洛谷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\) 很小，考虑状压dp。设 \(f_{S}\) 表示状态为 \(S\) 时对答案的贡献。

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

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

反之，如果它能在 \(S\) 中产生匹配，那么它的贡献其实已经在之前计算过了，下面我们会解释这一点。

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

可以发现，在添加了 \(i\) 之后，\(t_i\) 将不再满足 \(t_{t_i} \not\in S\) ，也就是说我们如此转移其实能够不重不漏的计算贡献。

当然我们完全可以考虑 \(i\) 在队尾会造成哪些影响，这样就不用每次都重复计算 \(T\) 的那个 \(\sum_{x \in T}\) 了。

那么对于原题，每个点有三条连边，其实是同理的，甚至转移方程都是一样的。

时间复杂度 \(\mathcal{O}(n2^n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#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;
    for(int i = 0; i < n; i++)
    {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        --e[i][0]; --e[i][1]; --e[i][2];
    }
    dp[0] = 0;
    for(int S = 1; S < (1 << n); S++)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
            if((S >> i) & 1) sum += 3 - calc(i);
        dp[S] = INF;
        for(int i = 0; i < n; i++)
            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;
}