BZOJ5180【Baltic2016】Cities <斯坦纳树>

Problem

【Baltic2016】Cities

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

给定$n$个点，$m$条双向边的图，其中有$k$个点是重要的，每条边都有一定的长度。
现在要你选定一些边来构成一个图，要使得$k$个重要的点相互连通，求边的长度和的最小值。

Input

共$m+2$行
第$1$行读入$n,k,m$，表示$n$个点，$k$个重要的点，$m$条边
第$2$行读入$k$个重要点的编号
第$3$至第$m+2$行，每行包括$3$个数字$a,b,c$，表示有一条从$a$到$b$长度为$c$的双向路径

Output

共$1$行，即最小长度和

Sample Input

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

Sample Output

11

HINT

$k\le5,\;n\le10^5,\;1\le m\le2\times10^5$

标签：斯坦纳树 状压DP

Solution

斯坦纳树裸题。

斯坦纳树的基本解法是状压$\mathrm{DP}$，压缩联通状态进行$\mathrm{DP}$，$f[s][i]$表示在$i$点，联通状态为$s$的最小花费。
有两种转移：

• 状态$s$可以通过两个状态组合而来，对于$s$的一个子集$t$，有$f[s][i]=\max(f[s][i],f[t][i]+f[s-t][i])$
• 状态$s$也可以在同层向邻接点扩展，即最短路中的松弛操作，对于边$u,v$，有$f[s][v]=\max(f[s][v],f[s][u]+Edge_{u,v})$，可以跑最短路更新。

此题有点卡，注意不要用SPFA，要用堆优Dijkstra。

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define mp make_pair
#define MAX_N 100000
using namespace std;
typedef long long lnt;
typedef pair<lnt,int> pli;
typedef priority_queue<pli> pri_que;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k; lnt f[32][MAX_N+5]; bool mrk[32][MAX_N+5];
vector <int> G[MAX_N+5]; vector <lnt> E[MAX_N+5]; pri_que que;
void insert(int u, int v, lnt c) {G[u].push_back(v), E[u].push_back(c);}
void addedge(int u, int v, lnt c) {insert(u, v, c), insert(v, u, c);}
int main() {
    read(n), read(k), read(m), memset(f, 0x3f, sizeof f);
    for (int i = 0, p; i < k; i++) read(p), f[1<<i][p] = 0;
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    for (int s = 1; s < (1<<k); s++) {
        for (int i = 1; i <= n; i++)
            for (int t = (s-1)&s; t; t = (t-1)&s)
                f[s][i] = min(f[s][i], f[t][i]+f[s^t][i]);
        for (int i = 1; i <= n; i++) que.push(mp(-f[s][i], i));
        while (!que.empty()) {
            int u = que.top().sec; que.pop();
            if (mrk[s][u]) continue; mrk[s][u] = true;
            for (int i = 0, v; i < (int)G[u].size(); i++)
                if (f[s][v = G[u][i]] > f[s][u]+E[u][i])
                    f[s][v] = f[s][u]+E[u][i], que.push(mp(-f[s][v], v));
        }
    }
    lnt mi = 1LL<<62;
    for (int i = 1; i <= n; i++)
        mi = min(mi, f[(1<<k)-1][i]);
    return printf("%lld\n", mi), 0;
}