BZOJ5180【Baltic2016】Cities <斯坦纳树>

Problem

【Baltic2016】Cities

Description

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

Input

共行
第行读入，表示个点，个重要的点，条边
第行读入个重要点的编号
第至第行，每行包括个数字，表示有一条从到长度为的双向路径

Output

共行，即最小长度和

Sample Input

Sample Output

HINT

标签：斯坦纳树 状压DP

Solution

斯坦纳树裸题。

斯坦纳树的基本解法是状压，压缩联通状态进行，表示在点，联通状态为的最小花费。
有两种转移：

状态可以通过两个状态组合而来，对于的一个子集，有
状态也可以在同层向邻接点扩展，即最短路中的松弛操作，对于边，有，可以跑最短路更新。

此题有点卡，注意不要用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;
}