题解：P10601 [NWERC 2006] Ticket to Ride

· · 题解

如果本题要求那八个城市全部互相连通，那么就是最小斯坦纳树的模板了，但是题目中只需要四对城市两两之间连通即可。

可以先跑一遍最小斯坦纳树，此时就能得到所有含有顶点 i 的包含 S 中的关键点的树的权值之和的最小值，即 dp_{i,S}，其中也有只包含一部分关键点的树。

接着就可以再进行一次状压 dp，设 ans_{S} 表示包含 S 中的关键点对的图（可以不连通）的最小权值和，其中 0\le S\le 15。那么转移的时候，就枚举 S 的子集 s，并更新 ans_S 的值，如果 ans_s+ans_{S\oplus s}<ans_S，则将 ans_S 赋值为 ans_s+ans_{S\oplus s}。ans_S 的初始化也不难，需要找到对应的 dp_{i,S'}。其中 i 需要找到 S 的一个点并对应找到它在 n 个点中的编号，而 S' 则复杂一些，需要找到 S 中所有点对，再把一个点对拆成两个点，具体方式可以参考代码。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=105,K=10;
int dp[N][1<<K];
bool vis[N];
vector<PII>e[N];
map<string,int>mp;
int n;
void dij(int S){
    memset(vis,0,sizeof(vis));
    priority_queue<PII,vector<PII>,greater<PII>>q;
    for(int i=1;i<=n;i++)if(dp[i][S]!=0x3f3f3f3f)q.push({dp[i][S],i});
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(PII t:e[x]){
            int y=t.first,w=t.second;
            if(dp[y][S]>dp[x][S]+w){
                dp[y][S]=dp[x][S]+w;
                q.push({dp[y][S],y});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;int k=8;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        mp[s]=i;
    }
    for(int i=1;i<=m;i++){
        string u,v;int w;cin>>u>>v>>w;
        e[mp[u]].push_back({mp[v],w});
        e[mp[v]].push_back({mp[u],w});
    }
    string s1,s2,s3,s4,s5,s6,s7,s8;cin>>s1>>s2>>s3>>s4>>s5>>s6>>s7>>s8;
    int p[9]={0,mp[s1],mp[s2],mp[s3],mp[s4],mp[s5],mp[s6],mp[s7],mp[s8]};
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=k;i++)dp[p[i]][1<<i-1]=0;
    for(int S=0;S<(1<<k);S++){
        for(int s=S;s;s=((s-1)&S)){
            for(int i=1;i<=n;i++)dp[i][S]=min(dp[i][S],dp[i][s]+dp[i][S^s]);
        }
        dij(S);
    }
    int ans[16]={0};
    //ans[S] 表示只让 S 中的这几对点互相连通的最小花费
    //转移时枚举子集 s，ans[S]=min(ans[S],ans[s]+ans[S^s])
    for(int S=1;S<16;S++){
        int i=__lg(S&(-S))+1;
        int x=0;for(int j=0;j<4;j++)if(S&(1<<j))x|=((1<<j*2)|(1<<j*2+1));
        ans[S]=dp[p[i*2]][x];
        for(int s=S;s;s=((s-1)&S)){
            ans[S]=min(ans[S],ans[s]+ans[S^s]);
        }
    }
    cout<<ans[15];
    return 0;
}