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

· · 题解

偶然看到这题还能提交题解来水一发

之前 ABC 的 G 题经常出这个啊，但我不会就白搭了吗。

令 dp_{i,|S|} 代表一个包含子集为 |S| 且包含 i 点的最小斯坦纳树。有两种转移，其一是将 dp_{i,|S|} 转移到 dp_{j,|S|}，代价为 (i,j) 之间的最短路，另一种是 dp_{i,|S|}=dp_{i,|T|}+dp_{i,|S/T|}，表示将两个子集合并。其中 |S/T| 表示在 S 集中但不在 T 集中的元素。

对每一个新的结果都要跑一遍 dijkstra，我的时间复杂度为 O(nm\log n+3^knk+3^kn\log n)。

为啥我代码没有火车头都能写得到 2.65K？ZYN 1.08K 结束了。并且他的代码的评测用时之和比我的最慢点还快一倍以上？

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=107;
const int M=5005;
int n,m,k;
int zdl[N][N];
int vis[N][N];
int dp[N][M];   //dp[i][j] 表示整个集合 j 整合在 i 号点上 
int pow2[20],pow3[20];
int point[20];
int point1[N];
vector<pair<int,int> > g[N];
void init(){
    memset(zdl,0x3f,sizeof(zdl));
    memset(point1,-1,sizeof(point1));
    memset(dp,0x3f,sizeof(dp));
    pow2[0]=pow3[0]=1;
    for(int i=1;i<=17;i++){
        pow2[i]=pow2[i-1]*2,pow3[i]=pow3[i-1]*3;
    } 
}  
void dijkstra(int st){
    priority_queue<pair<int,int> > q;
    q.push(make_pair(0,st));
    while(!q.empty()){
        int now1=q.top().second,now2=-q.top().first;
        q.pop();
        if(vis[st][now1])   continue;
        vis[st][now1]=1;
        for(int i=0;i<g[now1].size();i++){
            int v=g[now1][i].first,w=g[now1][i].second;
            if(zdl[st][v]>zdl[st][now1]+w){
                zdl[st][v]=zdl[st][now1]+w;
                q.push(make_pair(-zdl[st][v],v));
            }
        }
    }
    if(~point1[st]){
        int bitplace=pow2[point1[st]];
        if(!bitplace)   return;
        for(int i=1;i<=n;i++){
            //这里枚举停留在哪个点 
            dp[i][bitplace]=zdl[st][i]; 
//          cout<<i<<' '<<bitplace<<' '<<dp[i][bitplace]<<endl;
        }
    }
}
int vis1[107];
void dijkstra2(int zt){
    priority_queue<pair<int,int> > q;
    //这里是对 dp[停留位置][zt] 进行转移 
    for(int i=1;i<=n;i++){
        q.push(make_pair(-dp[i][zt],i));
        vis1[i]=0;
    } 
    while(!q.empty()){
        int now1=q.top().second;
        q.pop();
        if(vis1[now1])  continue;
        vis1[now1]=1;
        for(int i=0;i<g[now1].size();i++){
            int v=g[now1][i].first,w=g[now1][i].second;
            if(dp[v][zt]>dp[now1][zt]+w){
                dp[v][zt]=dp[now1][zt]+w;
                q.push(make_pair(-dp[v][zt],v));
            }
        }
    }
}
signed main(){
    init();
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w)),g[v].push_back(make_pair(u,w));
    }
    for(int i=0;i<k;i++){
        cin>>point[i],point1[point[i]]=i;
    }//全局中只有 point1 使用 0 开始排序  
    for(int i=1;i<=n;i++){
        zdl[i][i]=0;
        dijkstra(i);
    }
//  cout<<dp[1][1]<<endl;
    for(int i=1;i<pow3[k];i++){
        //三进制状压枚举子集 
        int x1=0,x2=0;  //代表两个子集的具体情况 
        int nowi=i;
        for(int j=0;j<k;j++){
            if(nowi%3==1)   x1+=pow2[j];
            else if(nowi%3==2)  x2+=pow2[j];
            nowi/=3;
            for(int l=1;l<=n;l++){
                dp[l][x1|x2]=min(dp[l][x1|x2],dp[l][x1]+dp[l][x2]);
            }
//          cout<<x1<<' '<<x2<<endl;
        }
        dijkstra2(x1|x2);
//      for(int j=1;j<=n;j++){
//          dp[j][x1|x2]=min(dp[j][x1|x2],dp[j][x1]+dp[j][x2]);
//          cout<<j<<' '<<(x1|x2)<<' '<<dp[j][x1|x2]<<endl;
//      }
    }
    int include13=1e18;
    for(int i=1;i<=n;i++){
        include13=min(include13,dp[i][pow2[k]-1]);
    }
    cout<<include13<<endl;
//  cout<<dp[6][15]<<endl;
    return 0;
}