「NOIP2017」宝藏

发表于 更新于 分类于

「NOIP2017」宝藏

不知道为什么，最开始\(70\)的暴力都没有想到。

因为当前在某个最新开发的点，不会再往以前已经开发的点连边。

所以开发顺序是一个排列，所以直接全排列枚举开发顺序。

每个新开发的点，都枚举是从哪个已开发的点过来的，这样做应该是\(\mathjaxcal{O}(n^3n!)\)的，可以拿\(70\)分。

然后这题有一个根据定义的状压\(dp\)，可以把开发顺序看成一棵\(bfs\)树，是一层一层开发的。

设\(f[i][s1][s2]\)表示已经开了前\(i\)层，开发的点集是\(s1\)，最后一层是\(s2\)，枚举\(s1\)补集的子集接上即可。

不知道为什么我写了这个\(\mathjaxcal{O}(n^24^n)\)的\(dp\)没过样例。

可以优化下状态，可以发现不用管第三维，因为最优状态总会被考虑到，只用记录\(g[i][j]\)表示两个集合连边的最小边权和。

转移的时候\(g[i][j]=g[i][j\and -j]+v\)

而\(f[i][s1]\)表示已经开了前\(i\)层，开发的点集是\(s1\)，枚举一下\(s1\)的子集作为最后一层即可转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << 12;
int f[M][M], g[N][M], n, m, nxt[M], w[N][N], lg[M];

int main() {
    memset(w, 0x3f, sizeof w);
    memset(g, 0x3f, sizeof g);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) lg[1 << i] = i;
    for (int i = 1; i <= m; i++) {
    	int u, v, val;
    	scanf("%d %d %d", &u, &v, &val);
    	u--, v--;
    	if (val < w[u][v]) w[u][v] = w[v][u] = val;
    }
    int S = (1 << n) - 1;
    for (int i = 1; i <= S; i++) {
    	int bu = S ^ i, v = 0;
    	for (int j = bu; j; j = (j - 1) & bu) nxt[j] = v, v = j;
    	for (int j = v; j; j = nxt[j]) {
    		v = 1e6;
            int x = lg[j & -j];
            for (int k = 0; k < n; k++) if (i & (1 << k)) v = min(v, w[k][x]);
            f[i][j] = f[i][j ^ (j & -j)] + v;
    	}
    }
    for (int i = 0; i < n; i++) g[0][1 << i] = 0;
    for (int l = 1; l < n; l++)
    	for (int i = 1; i <= S; i++)
    		for (int j = i; j; j = (j - 1) & i) {
    			g[l][i] = min(g[l][i], g[l - 1][i ^ j] + l * f[i ^ j][j]);
    		}
    int res = 1e9;
    for (int i = 0; i < n; i++) res = min(res, g[i][S]);
    printf("%d\n", res);
    return 0;
}