题解 P3264 【[JLOI2015]管道连接】

· · 题解

【解题思路】

考虑把问题拆开,先得到在任意多个频道间建设管道的费用方案(因为不同频道的重要情报站的管道建设若有交集就可以节省费用),最后枚举所有情况,合并得到总共 p 个频道的最小费用。

这时,对于任意多个频道,我们可以想到用斯坦纳树,就是构造包含这些关键点(重要情报站)的生成树的最小费用(因为是无向边,重要情报站之间互相连通)。

假设第 l~r 个频道一共有 \sum \limits^r_{i=l}P_i 个关键点,我们用 \sum \limits^r_{i=l}P_i 位二进制数表示关键点是否在生成树上的状态。

对于斯坦纳树,令 f[i][sta] 为一定包含点 i ,关键点状态为 sta 的最小费用。

f[i][sta] 有两种转移:

即转移前的两种状态都包含点 $i$,它们的状态可以合并为 $sta$,同时保持初始时费用最小。 $[2]. f[i][sta] = Min(f[j][sta] + cst[i][j])$(其中 $i$ 号点和 $j$ 号点有边相连,费用为 $cst[i][j]$) 即包含点 $i$ 的当前最小费用可以通过与之相连的中间点 $j$ 更新为更优的方案。但这样就存在一个问题,如果我们枚举 $i,j$ ,则 $i$ 可由 $j$ 转移过来,而 $j$ 也可由 $i$ 转移过来,这明显与实际矛盾。因此我们要对所有存在方案的点 $j$ 跑 $SPFA$,以此寻找可以更新的点 $i$,跑 $SPFA$ 的同时也就避免了上述的问题。 之后我们记 $g[sta'] = Min(f[i][(1 << \sum \limits^r_{i=l}P_i) - 1])$ ,$sta’$ 是用 $p$ 位二进制数表示频道是否连通的状态(**与 $f[i][sta]$ 中的状态 $sta$ 表示意义不同**),则 $g[sta']$ 表示频道状态为 $sta’$ 时的最优方案。 $g[sta']$ 的转移与 $f[i][sta]$ 的转移 $[1].$ 相同,也就是我们最上面所说的合并。即 $g[sta'] = Min(g[s'], g[sta' - s'])$($s'$ 为 $sta'$ 的子集)。 最后的答案为 $g[(1 << p) - 1]$,得到的方案也就是**斯坦纳树森林**。 **【AC代码】** ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int Maxn = 0x3f3f3f3f; const int N = 1005, M = 6005, L = 1 << 10; int lst[N], f[N][L], nxt[M], to[M], cst[M], g[L], c[12]; int n, m, k, T, Cn; bool vis[N]; queue<int> Q; template <class T> inline T Min(const T a, const T b) {return a < b? a : b;} template <class T> inline void CkMin(T &a, const T b) {if (a > b) a = b;} struct point { int col, id; #define col(x) a[x].col #define id(x) a[x].id }a[12]; inline bool cmp(const point x, const point y) {return x.col < y.col;} inline int get() { char ch; bool f = false; int res = 0; while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); if (ch == '-') f = true; else res = ch - '0'; while ((ch = getchar()) >='0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0'; return f? ~res + 1 : res; } inline void put(int x) { if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) put(x / 10); putchar(x % 10 + 48); } inline void add(const int x, const int y, const int z) { nxt[++T] = lst[x]; lst[x] = T; to[T] = y; cst[T] = z; nxt[++T] = lst[y]; lst[y] = T; to[T] = x; cst[T] = z; } inline void SPFA(const int I) { int x, y; while (!Q.empty()) { x = Q.front(); vis[x] = false; Q.pop(); for (int i = lst[x]; i; i = nxt[i]) if (f[y = to[i]][I] > f[x][I] + cst[i]) { f[y][I] = f[x][I] + cst[i]; if (!vis[y]) vis[y] = true, Q.push(y); } } } inline int solve(const int cnt) { int Cm = 1 << cnt; for (int i = 1; i < Cm; ++i) { for (int j = 1; j <= n; ++j) { for (int k = (i - 1) & i; k; k = (k - 1) & i) // 表示枚举子集:k不断减一就不会遗漏 // (k - 1) & i 表示状态 k 中包含的关键点总状态 i 中一定包含 CkMin(f[j][i], f[j][k] + f[j][i - k]); if (f[j][i] != Maxn) vis[j] = true, Q.push(j); } SPFA(i); } int res = Maxn; for (int i = 1; i <= n; ++i) CkMin(res, f[i][Cm - 1]); return res; } int main() { n = get(); m = get(); k = get(); int x, y; for (int i = 1; i <= m; ++i) { x = get(); y = get(); add(x, y, get()); } for (int i = 1; i <= k; ++i) col(i) = get(), id(i) = get(); sort(a + 1, a + k + 1, cmp); for (int i = 1; i <= k; ++i) { if (col(i) != col(i - 1)) Cn++; c[i] = Cn; } for (int i = 1; i <= k; ++i) col(i) = c[i]; //离散化 Cn = (1 << Cn); memset(g, Maxn, sizeof(g)); for (int i = 1; i < Cn; ++i) { memset(f, Maxn, sizeof(f)); int cnt = 0; for (int j = 1; j <= k; ++j) if ((1 << col(j) - 1) & i) f[id(j)][1 << cnt++] = 0; g[i] = solve(cnt); } for (int i = 1; i < Cn; ++i) for (int j = (i - 1) & i; j; j = (j - 1) & i) CkMin(g[i], g[j] + g[i - j]); return put(g[Cn - 1]), 0; } ```