题解：AT_abc364_g [ABC364G] Last Major City

· · 题解

成战犯了，我很晚才把这个题做出来。

前置知识：P6192 【模板】最小斯坦纳树

没有在板子的基础上有多少加强，但是必须使用优化最短路转移后的最小斯坦纳树算法。（如果你写的是 O(nm\log n+3^knk+3^kn\log n) 的就过不了，要搞 O(3^k(n+k)+2^kn\log n) 的版本）

因为在 [1,k-1) 区间外只有一个点，最小斯坦纳树的转移又形似 dp_{i,|S|}，考虑用 i 覆盖 [1,k) 区间以外的点，用 |S| 代表 \left \{ 1,2,3,\dots,k-1 \right \} 的全集。得到所有的答案。

注意本题中的关键点只有 k-1 个。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
} 
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
const int N=2*2025,M=2025,mod=1e9+9;    //mod 没有实际意义  
int n,m,k;
vector<pair<int,int> > g[N];

int dp[N][M];   //dp[i][S] 位置为 i 集合为 S 
int pow3[20];
void init(){
    pow3[0]=1;
    for(int i=1;i<=16;i++){
        pow3[i]=pow3[i-1]*3;    //其实这里用不着 mod 了  
    }
} 
int vis[N];
void dijkstra(int S){
    priority_queue<pair<int,int> > q;
    for(int i=1;i<=n;i++){
        q.push(mp(-dp[i][S],i));
        vis[i]=0;
    }
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])  continue;
        vis[u]=1;
//      cout<<'#'<<u<<' '<<dp[u][S]<<endl;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].first,w=g[u][i].second;
            if(dp[v][S]>dp[u][S]+w){
                dp[v][S]=dp[u][S]+w;
                q.push(mp(-dp[v][S],v));
            }
        }
    }
//  cout<<endl;
}
signed main(){
    init();
    for(int i=1;i<=4000;i++){
        for(int j=1;j<=1500;j++){
            dp[i][j]=1e15;
        }
    }
//  memset(dp,0x3f,sizeof(dp)); 
//  cout<<dp[0][0]<<endl; 
//  cout<<dp[0][0]*2<<endl;
//  cout<<dp[0][0]*3<<endl;
//  cout<<dp[0][0]*4<<endl;
//  cout<<dp[0][0]*5<<endl;
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        g[u].push_back(mp(v,w)),g[v].push_back(mp(u,w)); 
    } 
    for(int i=1;i<k;i++){
        dp[i][(1<<i)]=0;    //这些位置代价为 0  
    } 
    for(int i=1;i<pow3[k];i++){
        int now=i,a=0,b=0;  //分解成 a b 两个集合 
        for(int j=0;j<k;j++){
            int x=now%3;
            if(x==1)    a+=(1<<j);
            if(x==2)    b+=(1<<j);
            now/=3; 
        } 
        if(a%2) continue;   //注意 0 号点不存在 
        if(b%2) continue;   //同上 
        for(int j=1;j<=n;j++){
            dp[j][a+b]=min(dp[j][a+b],dp[j][a]+dp[j][b]);
        } 
        if(!a){
            dijkstra(a+b);
        }
    }
//  for(int S=1;S<=8;S++){
//      for(int i=1;i<=n;i++){
//          cout<<'#'<<S<<' '<<i<<' '<<dp[i][S]<<endl;
//      }
//  }
    for(int i=k;i<=n;i++){
        write2(dp[i][(1<<k)-2]);
    }
    putchar('\n');
    return 0;
}//痛快一起努力的感觉 我们拥有 同样的机会