洛谷P2210 Haywire 题解

题目链接：P2210 Haywire

题目描述

Farmer John 有 \(N\) 只奶牛（ \(4 \leq N \leq 12\)，\(N\) 是偶数）。

他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流。

每一头奶牛在这个牧场中正好有 \(3\) 个朋友，并且他们必须把自己安排在一排干草堆中。

一条长 \(L\) 的线路要占用刚好 \(L\) 堆干草来保护线路。

比如说，如果有两头奶牛分别在草堆 \(4\) 与草堆 \(7\) 中，并且他们是朋友关系，那么我们就需要用 \(3\) 堆干草来建造线路，使他们之间能够联系。

假设每一对作为朋友的奶牛都必须用一条单独的线路来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆。

输入格式

第 \(1\) 行：一个整数 \(N\)。为了方便，我们给奶牛用 \(1\sim N\) 的数字进行编号。

第 \(2, 3, \cdots, N + 1\) 行：每一行都有三个在 \(1\sim N\) 中的整数。第 \(i+1\) 行的数字代表着第 \(i\) 头奶牛的三个朋友的编号。显然，如果奶牛 \(i\) 是奶牛 \(j\) 的三个朋友之一，那么奶牛 \(j\) 也是奶牛 \(i\) 的三个朋友之一。

注：不存在自己是自己朋友的情况，或者单向朋友的情况。

输出格式

一个整数，代表着建造线路需要的干草堆数量的最小值。

本题主流解法都是模拟退火，因此本文来讲讲更靠谱而且更快的解法。

首先明确数据范围。题目规定了 \(n\) 为偶数，而且看出题人的措辞、数据范围等可以认为不存在自环和重边。

主要证据是，如果 \(n\) 为奇数，无法保证每个节点有且仅有 \(3\) 条边，\(\sum_{v\in V}\deg(v)=3n\) 一定为奇数。

加上确实没有自环和重边的数据，于是默认本题不存在自环和重边，开始讲做法。

注意到 \(n\) 很小，考虑状压dp。设 \(f(S)\) 表示状态为 \(S\) 时对最终答案的贡献，最终答案为 \(f(U)\) 。

这里 \(f(S)\) 的初始值设为 \(+\infty\) 并随后考虑转移，另外注意 \(f(S)\) 定义的是贡献，不能简单的等同于 \(S\) 的最优解。

因为这里的贡献计算比较难以理解，所以我们首先考虑每个点只有一条边的情况。

考虑 \(f(S)\) 的转移，我们每次钦定最优排列的队尾为 \(i\,(i \in S)\) ，不妨记 \(T = S \setminus \{i\}\) ，则 \[ f(S) \gets \min\left(f(S),\ f(T) + \sum_{x \in T}\left(1 - \mathbf{1}_T(t_x)\right)\right) \] 其中 \(t_x\) 表示与 \(x\) 有连边的那个点，\(\mathbf{1}_T(t_x)\) 为指示函数。

以及这里队尾指的是，当 \(S\) 中的点按照最优排列中的相对顺序排好队后，排在队列最后的那个元素。

这里 \(\sum_{x \in T}\left(1 - \mathbf{1}_T(t_x)\right)\) 计算的是所有未匹配成功的 \(t_x\)，它在这一轮转移中需要贡献未匹配的花费 \(1\)。

我们考察任意 \(S\) 中的每个点，如果它不能在 \(S\) 中产生匹配，则它的贡献为它在最优排列下到队尾的距离。

反之，如果它能在 \(S\) 中产生匹配，那么它的贡献一定已经在之前计算过了，因此统计是不重不漏的。

直接算的话时间复杂度为 \(O(n^22^n)\) ，我怀疑 std 就是这么写的，不过我们还能进行优化。

注意到从 \(T\) 变为 \(S\) 后，这轮被匹配的 \(t_i\) 将不再产出贡献，而这轮未匹配的 \(t_i\) 将继续产生贡献，即 \[ \begin{aligned} \sum_{x \in T}\left(1 - \mathbf{1}_T(t_x)\right) &= \sum_{x \in S}\left(1 - \mathbf{1}_S(t_x)\right)-(1-\mathbf{1}_T(t_i)) + \mathbf{1}_T(t_i) \\[6pt] &= \sum_{x \in S}\left(1 - \mathbf{1}_S(t_x)\right)-(1-\mathbf{1}_S(t_i)) +\mathbf{1}_S(t_i) \end{aligned} \] 如果觉得上面这个式子意义不明，那么这实际上是为原题的三条边的情况预留的形式，往下看。

这样每次转移之前提前算好 \(\sum_{x \in S}\left(1 - \mathbf{1}_S(t_x)\right)\) 的值，然后转移的时候就能 \(O(1)\) 算 \(f(T)\) 后面的贡献增量了。

那么对于原题，每个点有三条连边，其实是同理的，只不过 \(t_i\) 变成了 \(t_{i,0},t_{i,1},t_{i,2}\) ，稍微改一下式子就好了。 \[ f(S) \gets \min\left(f(S),\ f(T) + \sum_{x \in T}\left(3 - \sum_{j=0}^{2}\mathbf{1}_T(t_{x,j})\right)\right) \] 以及优化后的里面那一堆 \[ \sum_{x \in T}\left(3 - \sum_{j=0}^{2}\mathbf{1}_T(t_{x,j})\right) = \sum_{x \in S}\left(3 - \sum_{j=0}^{2}\mathbf{1}_S(t_{x,j})\right) -\left(3-\sum_{j=0}^{2}\mathbf{1}_S(t_{i,j})\right)+\sum_{j=0}^{2}\mathbf{1}_S(t_{i,j}) \] 这个式子也只是看着吓人而已，代码写起来非常简单。

时间复杂度 \(O(n2^n)\) ，轻松通过本题

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

int dp[1 << 12], e[14][3];
#define calc(i) (((S >> e[i][0]) & 1) + ((S >> e[i][1]) & 1) + ((S >> e[i][2]) & 1))
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 0, n - 1)
    {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        --e[i][0]; --e[i][1]; --e[i][2];
    }
    dp[0] = 0;
    rep(S, 1, (1 << n) - 1)
    {
        int sum = 0;
        rep(i, 0, n - 1) if((S >> i) & 1) { sum += 3 - calc(i); }
        dp[S] = INF;
        rep(i, 0, n - 1) if((S >> i) & 1)
        {
            int cost = sum - (3 - calc(i)) + calc(i);
            down(dp[S], dp[S ^ (1 << i)] + cost);
        }
    }
    cout << dp[(1 << n) - 1] << '\n';
    return 0;
}

另外这个东西和最小线性排列（Minimum Linear Arrangement Problem）很像，后者是 NP-Hard 问题。

参考文献：

[1] https://gyrojeff.top/index.php/archives/P2210-Haywire-%E7%8A%B6%E5%8E%8B-DP/