题解 P6192【【模板】最小斯坦纳树】

· · 题解

\text{Link}

题意

给出一张 n 个点，m 条有权边的无向连通图，其中有 k 个点是关键点。求图的一个子图，满足包含了所有 k 个关键点，使得所包含的边集的权值和最小，求这个最小值。

## 思路 首先，我们要知道答案子图是一颗树，因为如果其上有个环，可以断开环上任意一条边，点集不会变化但答案会变小。 考虑状压 $\text {dp}$，设 $dp_{i,S}$ 表示以 $i$ 为根的答案中包含了关键点集合 $S$ 时的答案。 有两种情况：$i$ 的度为 $1$ 或大于 $1$。 - 若 $i$ 的度数为 $1

考虑其与 j 相连，则有转移

dp_{j,S}+w_{(i,j)}\to dp_{i,S}

再考虑用 j 更新 i，可以考虑使用最短路算法，用 dp_{j,S} 更新所有 dp_{i,S}，再用被更新的继续更新其它值。

dp_{j,S}+dis_{i,j}\to dp_{i,S}

这部分时间复杂度是 O(2^k\times nm) 的。

考虑 i 可以划分成两个子集之并，枚举 S 的子集，用它与其补集的答案之和更新 dp_{i,S}，即

dp_{i,S}\gets dp_{i,T},dp_{i,S\backslash T}

这里简单说明一下枚举子集的时间复杂度：

&=\sum_{k=0}^n2^k\binom{n}{k}\\ &=\sum_{k=0}^{n}2^{k}1^{n-k}\binom{n}{k}\\ &=3^n\\ \end{aligned}

所以这部分时间复杂度是 O(n\times 3^k) 的。

总时间复杂度就是 O(n\times 3^k+nm\times 2^k) 的，这里用 \text{SPFA} 比 \text{Dijkstra} 快很多。

另外，满足题目要求的树为斯坦纳树，这个算法构建出来的树被称为最小斯坦纳树。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff

}
const int N=100+10,K=10;
int n,m,k,p[N],up;
int cnt,head[N];
int dp[N][1<<K];
struct Edge{
    int to,nxt,w;
}a[N*10];
inline void add(int u,int v,int w){
    cnt++;
    a[cnt].to=v;
    a[cnt].w=w;
    a[cnt].nxt=head[u];
    head[u]=cnt;
}
queue<int>q;
bool vis[N];
inline void SPFA(int s){
    while(!q.empty()){
        int rt=q.front();
        q.pop();
        vis[rt]=0;
        for(int i=head[rt];i;i=a[i].nxt){
            int t=a[i].to;
            if(dp[t][s]>dp[rt][s]+a[i].w){
                dp[t][s]=dp[rt][s]+a[i].w;
                if(!vis[t])
                    q.push(t),vis[t]=1;
            }
        }
    }
}
int main(){
    memset(dp,127/3,sizeof(dp));
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w); 
    }
    for(int i=1;i<=k;i++){
        p[i]=read();
        dp[p[i]][1<<i-1]=0;
    }
    up=(1<<k)-1;
    for(int s1=0;s1<=up;s1++){
        for(int i=1;i<=n;i++){
            for(int s2=s1&s1-1;s2;s2=s2-1&s1)
                dp[i][s1]=min(dp[i][s1],dp[i][s2]+dp[i][s1^s2]);
            if(dp[i][s1]<1e9)
                q.push(i),vis[i]=1;
        }
        SPFA(s1);
    } 
    write(dp[p[1]][up]);
    flush();
}

再见 qwq~