首页 > 代码库 > BZOJ3058 四叶草魔杖
BZOJ3058 四叶草魔杖
Poetize11的T3
蒟蒻非常欢脱的写完了费用流，发现。。。边的cost竟然只算一次！！！
然后就跪了。。。
Orz题解："类型：Floyd传递闭包+最小生成树+状态压缩动态规划
首先Floyd传递闭包，然后找出所有∑ai =0的集合，对每个集合求出最小生成树，就是该集合内部能量转化的最小代价。
然后把每个集合当做一个物品，做一遍类似背包的DP。DP过程中F[i]表示二进制状态为i（1表示该点选了，0表示没选）时已选的点之间能量转化的最小代价。然后枚举所有的j，如果i and j=0，那么用F[i]+F[j]更新一下F[i or j]。
直接这样DP可能会超时，我们不妨去除一些诸如ai=0之类的点。然后把∑ai=0的集合存进数组，DP时只循环数组内的状态来加速。"
原来Floyd还有如此妙用= =
1 /************************************************************** 2 Problem: 3058 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:36 ms 7 Memory:1580 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 const int N = 20, M = 65536;16 17 int n, m, p, q, l, t;18 int a[N], d[N][N], g[N], b[M], c[N], f[M], s[M];19 bool vis[N];20 21 inline int read() {22 int x = 0, sgn = 1;23 char ch = getchar();24 while (ch < ‘0‘ || ‘9‘ < ch) {25 if (ch == ‘-‘) sgn = -1;26 ch = getchar();27 }28 while (‘0‘ <= ch && ch <= ‘9‘) {29 x = x * 10 + ch - ‘0‘;30 ch = getchar();31 }32 return sgn * x;33 }34 35 int prim() {36 int res = 0, i, j, k, tmp;37 memset(vis, 0, sizeof(vis));38 memset(g, 0x3f, sizeof(g));39 g[c[1]] = 0;40 for (i = 1; i <= m; ++i) {41 tmp = 0x3fffffff;42 for (j = 1; j <= m; ++j)43 if (!vis[c[j]] && g[c[j]] < tmp) tmp = g[c[j]], k = c[j];44 if (tmp == 0x3f3f3f3f) return -1;45 res += tmp;46 vis[k] = 1;47 for (j = 1; j <= m; ++j)48 if (!vis[c[j]] && g[c[j]] > d[k][c[j]])49 g[c[j]] = d[k][c[j]];50 }51 return res;52 }53 54 void Floyd() {55 int i, j, k;56 for (k = 1; k <= n; ++k)57 for (i = 1; i <= n; ++i)58 for (j = 1; j <= n; ++j)59 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);60 }61 62 int main() {63 int i, j, k, x, y, maxi;64 n = read(), m = read();65 memset(d, 0x3f, sizeof(d));66 t = (1 << n) - 1;67 for (i = 1; i <= n; ++i) {68 if (!(a[i] = read())) t ^= 1 << i - 1;69 d[i][i] = 0;70 }71 for (i = 1; i <= m; ++i) {72 x = read() + 1, y = read() + 1;73 d[x][y] = d[y][x] = read();74 }75 Floyd();76 memset(f, 0x3f, sizeof(f));77 f[0] = 0;78 for (p = i = 0, maxi = 1 << n; i < maxi; ++i) {79 for (j = 0; j < n; ++j)80 if ((i >> j & 1) && !a[j + 1]) break;81 if (j < n) continue;82 b[i] = 0;83 for (m = j = 0; j < n; ++j)84 if (i >> j & 1) b[i] += a[j + 1], c[++m] = j + 1;85 if (b[i]) continue;86 b[i] = prim();87 s[++p] = i;88 }89 for (q = 2; q <= p; ++q) {90 i = s[q], k = b[i];91 if (k == -1) continue;92 for (l = 1; l <= p; ++l) {93 j = s[l];94 if (!(i & j)) f[i | j] = min(f[i | j], f[j] + k);95 }96 }97 if (f[t] == 0x3f3f3f3f) puts("Impossible");98 else printf("%d\n", f[t]);99 }
BZOJ3058 四叶草魔杖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。