裸的状压DP

令$f_S$表示包含颜色集合S的最小斯坦纳生成森林的值,于是有:

$$f_S=\min\{f_S,f_s+f_{S-s}|s\subset S\}$$

然后嘛。。。还是裸的斯坦纳树搞搞。。。又是个状压【摔!

貌似会TLE的说【额。。。

然后PoPoQQQ大爷分析了一番,说,大概1E的复杂度,不会T!

好,那就不会好了!(也太不求上进了吧)

 /**************************************************************
Problem: 4006
User: rausen
Language: C++
Result: Accepted
Time:7272 ms
Memory:5160 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int M = 3e3 + ;
const int N = 1e3 + ;
const int K = ;
const int Sz_q = N * ;
const int inf = 0x3f3f3f3f; inline int read(); struct edge {
int next, to, v;
edge(int _n = , int _t = , int _v = ) : next(_n), to(_t), v(_v) {}
} e[M << ]; struct point {
int c, w; inline void get() {
c = read(), w = read();
} inline bool operator < (const point &p) const {
return c < p.c;
}
} p[K]; int n, m, k, c, cnt;
int first[N], tot;
int f[][N], g[];
int l, r, q[Sz_q], v[N]; inline void Add_Edges(int x, int y, int z) {
e[++tot] = edge(first[x], y, z), first[x] = tot;
e[++tot] = edge(first[y], x, z), first[y] = tot;
} #define y e[x].to
void spfa(int *dis) {
static int x, p;
while (l != (r + ) % Sz_q) {
p = q[l], v[p] = , ++l %= Sz_q;
for (x = first[p]; x; x = e[x].next)
if (dis[p] + e[x].v < dis[y]) {
dis[y] = dis[p] + e[x].v;
if (!v[y]) {
v[y] = ;
if (dis[y] < dis[q[l]]) q[(l += Sz_q - ) %= Sz_q] = y;
else q[++r %= Sz_q] = y;
}
}
}
}
#undef y int work() {
static int S, s, i, res;
for (S = ; S < << cnt; ++S) {
for (i = ; i <= n; ++i) {
for (s = S & (S - ); s; (--s) &= S)
f[S][i] = min(f[S][i], f[s][i] + f[S ^ s][i]);
if (f[S][i] != inf) q[++r %= Sz_q] = i;
}
spfa(f[S]);
}
for (res = inf, i = ; i <= n; ++i)
res = min(res, f[( << cnt) - ][i]);
return res;
} int main() {
int i, x, y, z, S, s, nowc;
n = read(), m = read(), k = read();
for (i = ; i <= m; ++i) {
x = read(), y = read(), z = read();
Add_Edges(x, y, z);
}
for (i = ; i <= k; ++i) p[i].get();
sort(p + , p + k + );
for (nowc = -, c = , i = ; i <= k; ++i) {
if (p[i].c != nowc) nowc = p[i].c, ++c;
p[i].c = c;
} memset(g, 0x3f, sizeof(g));
for (S = ; S < << c; ++S) {
for (cnt = , i = ; i <= k; ++i)
if (S & ( << p[i].c - )) ++cnt;
memset(f, 0x3f, sizeof(f[][]) * N * ( << cnt));
for (cnt = , i = ; i <= k; ++i)
if (S & ( << p[i].c - )) f[ << cnt++][p[i].w] = ;
g[S] = work();
}
for (S = ; S < << c; ++S)
for (s = S & (S - ); s; (--s) &= S)
g[S] = min(g[S], g[s] + g[S ^ s]);
printf("%d\n", g[( << c) - ]);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}
05-08 08:11