Steiner Tree
Steiner Tree
Problem
给定一个点集，求权值和最小的一个边集使得这些点联通。可以连接到这些点以外的点。
Solution
这个组合最优化问题是 NP-hard 的。
我们考虑使用状压来指数级别枚举。
令 $ f_{i,S}:= $ 包含点 $ i $ 且连接点集中的状态为 $ S $ 的最小花费，可见有以下转移：
$$ f_{i,S}\leftarrow \begin{cases} f_{i,s}+f_{i,S\setminus s} \\ f_{j,S}+w(i,j) & \text{if }(i,j) \in E \end{cases} $$
第二类情况是反直觉的。但只要注意到定义之中我们的 $ i $ 并不一定包含在 $ S $ 以内，就容易知道只有第一种情况是不完备的。
处理第一种情况只是简单的子集枚举 DP。
考虑处理第二种情况。在固定 $ S $ 的情况下满足三角形不等式，所以可以直接用最短路模型来搞。
BZOJ 2595
$ n \times m $ 的网格图，一些点是景点（设有 $ k $ 个），剩下是空地，每一个空地上有些志愿者。
选取最少的志愿者使得经典联通。$ n,m,k\le 10 $.
Sol.
直接按上述做法搞即可。
Code(116056 kb, 1456 ms)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 15, INF = 0x3f3f3f3f;
int a[maxn][maxn], dp[maxn][maxn][1 << maxn];
queue<pair<int, int> > Q;
bool inq[maxn][maxn];
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct T
{
int x, y, z;
T(int a = -1, int b = -1, int c = -1){x = a, y = b, z = c;}
} pre[maxn][maxn][1 << maxn];
int n, m;
void go(int S)
{
while(!Q.empty())
{
int ux = Q.front().first, uy = Q.front().second; Q.pop();
for(int i = 0; i < 4; ++i)
{
int vx = ux + dx[i], vy = uy + dy[i];
if(vx < 0 || vx >= n || vy < 0 || vy >= m) continue;
if(dp[vx][vy][S] > dp[ux][uy][S] + a[vx][vy])
{
dp[vx][vy][S] = dp[ux][uy][S] + a[vx][vy];
pre[vx][vy][S] = T(ux, uy, S);
if(!inq[vx][vy]) Q.push(make_pair(vx, vy)), inq[vx][vy] = true;
}
}
inq[ux][uy] = false;
}
}
bool vis[maxn][maxn];
void dfs(int i, int j, int s)
{
vis[i][j] = true;
T t = pre[i][j][s];
if(t.x == -1 && t.y == -1) return;
dfs(t.x, t.y, t.z);
if(t.x == i && t.y == j) dfs(t.x, t.y, s - t.z);
}
int main()
{
read(n, m);
int k = 0;
memset(dp, INF, sizeof dp);
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
{
read(a[i][j]);
if(a[i][j] == 0) dp[i][j][1 << k] = 0, ++k;
}
int N = 1 << k;
for(int S = 0; S < N; ++S)
{
if(S == N - 1)
int a = 0;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
{
for(int s = S & (S - 1); s; s = (s - 1) & S)
{
int k = dp[i][j][s] + dp[i][j][S - s] - a[i][j];
if(k < dp[i][j][S]) dp[i][j][S] = k, pre[i][j][S] = T(i, j, s);
}
if(dp[i][j][S] < INF) Q.push(make_pair(i, j)), inq[i][j] = true;
}
go(S);
}
int x = -1, y = -1;
for(int i = 0; i < n && x == -1; ++i) for(int j = 0; j < m && x == -1; ++j) if(a[i][j] == 0) x = i, y = j;
dfs(x, y, N - 1);
printf("%d\n", dp[x][y][N - 1]);
for(int i = 0; i < n; ++i, puts("")) for(int j = 0; j < m; ++j)
if(a[i][j] == 0) putchar('x');
else if(vis[i][j]) putchar('o');
else putchar('_');
return 0;
}BZOJ 4774
$ n $ 点 $ m $ 边，选出权值最小的一个边集使得 $ i,n-i+1,\forall1\le i\le d $ 联通。
$ n,m\le10^4,1\le d\le 4 $.
Sol.
把 ST 处理出来。
注意到 ST 可能存在配对的边不相连通的情况（其实应该叫做 Steiner Trees），所以还要在做一次子集 DP.
Code(41180 kb, 5904 ms)
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 10, maxm = 1e4 + 10, INF = 0x3f3f3f3f;
struct E{int v, n, w;}e[maxm << 1];
int h[maxm], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
queue<int> Q; bool inq[maxm];
int f[maxm][1 << maxn], g[1 << maxn];
int main()
{
int n, m, d, k = 0; read(n, m, d);
memset(f, INF, sizeof f);
for(int i = 1; i <= d; ++i) f[i][1 << k] = 0, ++k;
for(int i = n; i > n - d; --i) f[i][1 << k] = 0, ++k;
int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
int N = 1 << k;
for(int S = 1; S < N; ++S)
{
for(int u = 1; u <= n; ++u)
{
for(int s = S & (S - 1); s; s = (s - 1) & S)
f[u][S] = min(f[u][S], f[u][s] + f[u][S - s]);
if(f[u][S] < INF) Q.push(u), inq[u] = true;
}
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inq[u] = false;
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(f[v][S] > f[u][S] + e[i].w)
{
f[v][S] = f[u][S] + e[i].w;
if(!inq[v]) Q.push(v), inq[v] = true;
}
}
}
memset(g, INF, sizeof g);
N = 1 << d;
for(int S = 1; S < N; ++S) for(int u = 1; u <= n; ++u) g[S] = min(g[S], f[u][S | (S << d)]);
for(int S = 1; S < N; ++S) for(int s = S & (S - 1); s; s = (s - 1) & S) g[S] = min(g[S], g[s] + g[S - s]);
printf("%d", g[N - 1] == INF ? -1 : g[N - 1]);
return 0;
}BZOJ 4006
给定一个图，有一些频道，包含一些点，要求频道内的点联通。求最小代价。
$ n \le 1000, m\le 3000, p \le 10 $.
Sol.
求 STs. 然后再对每一个频道枚举一次子集合并。
Code(129828kb, 22016ms)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1000 + 5, maxm = 3000 + 5, maxp = 10 + 5, INF = 0x3f3f3f3f;
struct E{int v, n, w;}e[maxm << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
queue<int> Q; bool inq[maxn];
map<int, int> mm;
int mc = 1;
int ma[1 << maxp], f[maxn][1 << maxp], g[1 << maxp];
int main()
{
int n, m, p; read(n, m, p);
int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
memset(f, INF, sizeof f); //memset(ma, INF, sizeof ma);
int c, d, k = 0; while(p--) read(c, d), (!mm[c] ? mm[c] = mc++ : true), f[d][1 << k] = 0, ma[1 << mm[c] - 1] |= 1 << k, k++;
int N = 1 << k;
for(int S = 1; S < N; ++S)
{
for(int u = 1; u <= n; ++u)
{
for(int s = S & (S - 1); s; s = (s - 1) & S) f[u][S] = min(f[u][S], f[u][s] + f[u][S - s]);
if(f[u][S] < INF) Q.push(u);
}
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inq[u] = false;
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(f[v][S] > f[u][S] + e[i].w)
{
f[v][S] = f[u][S] + e[i].w;
if(!inq[v]) Q.push(v), inq[v] = true;
}
}
}
memset(g, INF, sizeof g);
N = 1 << mc - 1;
for(int S = 1; S < N; ++S)
ma[S] = ma[S - (S & -S)] | ma[S & -S];
for(int S = 1; S < N; ++S) for(int i = 1; i <= n; ++i)
g[S] = min(g[S], f[i][ma[S]]);
for(int S = 1; S < N; ++S) for(int s = S & (S - 1); s; s = (s - 1) & S)
g[S] = min(g[S], g[s] + g[S - s]);
printf("%d\n", g[N - 1]);
return 0;
}