题解 P3264 【[JLOI2015]管道连接】
Log_x
·
·
题解
【解题思路】
考虑把问题拆开,先得到在任意多个频道间建设管道的费用方案(因为不同频道的重要情报站的管道建设若有交集就可以节省费用),最后枚举所有情况,合并得到总共 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;
}
```