题面

https://www.luogu.com.cn/problem/P2210

题解

一开始没反应出来是状压,看了少数题解才知道可以状压。今天姑且 A 掉状压的写法,明天写写看模拟退火。

首先,我们来设状压的状态方程:

$$
f[i]
$$

  • $i$ 代表 $i$ 表示成二进制的时候有 $1$ 那些位所代表的牛组成的集合
  • 比方说 $i = 6 = (110)_2$ 代表有 $2, 3$ 号牛组成的集合
  • $f[i]$ 代表牛的集合为 $i$ 时对答案产生的贡献。

什么是贡献?这个说法很模棱两可。其实是这样的:两个朋友都在集合里面,那答案必然要包括这对朋友连线的贡献。但是如果只有一头牛在集合里呢?很简单,贡献就是:按照某种最佳排列时,这头牛所处的位置到集合队尾的距离。这么说很抽象,我们举个例子:

$$
~ * ~ * ~ * ~ \triangle ~ * ~ *
$$

上图中,$*$ 代表无所谓的某头牛,$\triangle$ 代表我们现在考察的单个朋友,在这个状态下,$\triangle$ 对答案的贡献就是 $2$,因为 $\triangle$ 之后还有两头牛.

而如果在这个队列之后紧跟就是 $\triangle$ 的朋友:另一个 $\triangle$,那么在增加前 $\triangle$ 给出的贡献 $2$ 就是这对朋友对答案的贡献了:

$$
~ * ~ * ~ * ~ \triangle ~ * ~ * ~ \triangle
$$

好。赘述完关于状态的定义,我们来思考状态怎么转移。对于集合 $i$,我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给出的代码是做了一些小的优化,稍微难以理解,所以下面给出一个等价的形式,但是时间复杂度多一个 $n$,为 $O(n^22^n)$:

for (int i = 1; i < (1 << n); i ++) {
    for (int j = 0; j < n; j ++) {
        if ((1 << j) & i) {
            int pending_links = 0;
            int ii = i & ~(1 << j);
            for (int k = 0; k < n; k ++)
                if ((1 << k) & ii)
                    pending_links += 3 - 
                        (((ii >> nbr[k][0]) & 1) + 
                        ((ii >> nbr[k][1]) & 1) + 
                        ((ii >> nbr[k][2]) & 1));
            f[i] = min(f[i], f[ii] + pending_links);
        }
    }
}

代码

最终给出的代码时间复杂度为 $O(n2^n)$:

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 12;

int f[1 << maxn], nbr[maxn + 5][3];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> nbr[i][0] >> nbr[i][1] >> nbr[i][2];
        nbr[i][0] --; nbr[i][1] --; nbr[i][2] --;
    }
    memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < (1 << n); i ++) {
        int pending_links = 0;
        for (int j = 0; j < n; j ++)
            if ((1 << j) & i)
                pending_links += 3 - 
                    (((i >> nbr[j][0]) & 1) + 
                    ((i >> nbr[j][1]) & 1) + 
                    ((i >> nbr[j][2]) & 1));
        for (int j = 0; j < n; j ++) {
            if ((1 << j) & i) {
                f[i] = min(f[i], f[i & ~(1 << j)] + pending_links - (3 - 
                    (((i >> nbr[j][0]) & 1) + 
                    ((i >> nbr[j][1]) & 1) + 
                    ((i >> nbr[j][2]) & 1))) + 
                    ((i >> nbr[j][0]) & 1) + 
                    ((i >> nbr[j][1]) & 1) + 
                    ((i >> nbr[j][2]) & 1));
            }
        }
    }
    cout << f[(1 << n) - 1] << endl;
    return 0;
}
最后修改:2022 年 04 月 07 日 11 : 05 PM
真的不买杯奶茶嘛....qwq