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还有如此妙用= =
/**************************************************************
Problem: 3058
User: rausen
Language: C++
Result: Accepted
Time:36 ms
Memory:1580 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = , M = ; int n, m, p, q, l, t;
int a[N], d[N][N], g[N], b[M], c[N], f[M], s[M];
bool vis[N]; inline int read() {
int x = , sgn = ;
char ch = getchar();
while (ch < '' || '' < ch) {
if (ch == '-') sgn = -;
ch = getchar();
}
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return sgn * x;
} int prim() {
int res = , i, j, k, tmp;
memset(vis, , sizeof(vis));
memset(g, 0x3f, sizeof(g));
g[c[]] = ;
for (i = ; i <= m; ++i) {
tmp = 0x3fffffff;
for (j = ; j <= m; ++j)
if (!vis[c[j]] && g[c[j]] < tmp) tmp = g[c[j]], k = c[j];
if (tmp == 0x3f3f3f3f) return -;
res += tmp;
vis[k] = ;
for (j = ; j <= m; ++j)
if (!vis[c[j]] && g[c[j]] > d[k][c[j]])
g[c[j]] = d[k][c[j]];
}
return res;
} void Floyd() {
int i, j, k;
for (k = ; k <= n; ++k)
for (i = ; i <= n; ++i)
for (j = ; j <= n; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
} int main() {
int i, j, k, x, y, maxi;
n = read(), m = read();
memset(d, 0x3f, sizeof(d));
t = ( << n) - ;
for (i = ; i <= n; ++i) {
if (!(a[i] = read())) t ^= << i - ;
d[i][i] = ;
}
for (i = ; i <= m; ++i) {
x = read() + , y = read() + ;
d[x][y] = d[y][x] = read();
}
Floyd();
memset(f, 0x3f, sizeof(f));
f[] = ;
for (p = i = , maxi = << n; i < maxi; ++i) {
for (j = ; j < n; ++j)
if ((i >> j & ) && !a[j + ]) break;
if (j < n) continue;
b[i] = ;
for (m = j = ; j < n; ++j)
if (i >> j & ) b[i] += a[j + ], c[++m] = j + ;
if (b[i]) continue;
b[i] = prim();
s[++p] = i;
}
for (q = ; q <= p; ++q) {
i = s[q], k = b[i];
if (k == -) continue;
for (l = ; l <= p; ++l) {
j = s[l];
if (!(i & j)) f[i | j] = min(f[i | j], f[j] + k);
}
}
if (f[t] == 0x3f3f3f3f) puts("Impossible");
else printf("%d\n", f[t]);
}