题解：AT_abc395_g [ABC395G] Minimum Steiner Tree 2

· · 题解

很厉害的题，硬控我一天，让我又补完一场 ABC。

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

因为是要加入两个点，所以考虑把第一个点放入集合，作为第 k+1 个集合中的点。

接下来就转化成了 ABC364G 的那个问题，考虑 dp_{i,|S|} 代表集合 |S| 与 i 相连通的最小代价，用 |S| 包含点 [1,k] 和自己取的第 k+1 个点。i 代表第 k+2 个点。

本题 Floyd 转移最短路是没有问题的，建议直接使用 Floyd。

朴素最小斯坦纳树的时间复杂度为 O(3^k(n+k)+2^kn\log n)，本题因为是 Floyd 转移，并且要枚举第 k+1 个点，所以时间复杂度达到了 O(3^kn^2+2^kn^3)。不过还是能过的。

#include<bits/stdc++.h>
#define int long long
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=107;
const int M=2007;
int n,k,q;
int C[N][N];
int dp[N][M][N];    //dp[k+1][S][j] 选取的 k+1 个点为 k+1 集合为 S 目前到了 j  
int key[12];    //注意 key 的最后一位会动态修改 
int pow3[12];
void init(){
    pow3[0]=1;
    for(int i=1;i<=10;i++){
        pow3[i]=pow3[i-1]*3;
    }
} 
signed main(){
    init();
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            C[i][j]=read();
        }
    }
    for(int k_=1;k_<=n;k_++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                C[i][j]=min(C[i][j],C[i][k_]+C[k_][j]);
            }
        }
    }
    for(int i=1;i<=k;i++){
        key[i]=i;
    }
    memset(dp,0x3f,sizeof(dp)); 
    for(int i=1;i<=n;i++){
        dp[i][1<<k][i]=0;
    }
    for(int new_=k+1;new_<=n;new_++){
        //new_ 是第 k+1 个点 
        key[k+1]=new_;
        //然后跑一般的 minimum steiner tree 即可 
        for(int i=1;i<=k+1;i++){
            dp[new_][1<<(i-1)][key[i]]=0;   //代表这个时候先处理为 0 
//          cout<<'#'<<new_<<' '<<(1<<(i-1))<<' '<<key[i]<<' '<<0<<endl; 
        } 
        for(int i=1;i<pow3[k+1];i++){
            int now=i,a=0,b=0;  //分成 a b 两个子集 
            for(int j=0;j<k+1;j++){
                int x=now%3;
                if(x==1)    a+=(1<<j);
                if(x==2)    b+=(1<<j);
                now/=3;
            } 
            for(int j=1;j<=n;j++){
                dp[new_][a|b][j]=min(dp[new_][a|b][j],dp[new_][a][j]+dp[new_][b][j]);
//              cout<<(a|b)<<' '<<new_<<' '<<j<<' '<<dp[new_][a|b][j]<<endl;
            }
            if(a==0){
                for(int j=1;j<=n;j++){
                    //转移的都是 dp[new_][a|b][j]
                    for(int k_=1;k_<=n;k_++){
                        dp[new_][a|b][j]=min(dp[new_][a|b][j],dp[new_][a|b][k_]+C[k_][j]);
//                      cout<<(a|b)<<' '<<new_<<' '<<j<<' '<<dp[new_][a|b][j]<<endl;
                    } 
                }
            } 
        }
    } 
    q=read();
    while(q--){
        int x=read(),y=read();
        write2(dp[x][(1<<(k+1))-1][y]);
    }
    putchar('\n');
    return 0;
}//天青青等烟雨 而我在等你

其实本题我一直有一种错误思路，就是设 dp_{i,j,|S|} 代表路经 i,j 点且集合为 |S| 的情况。时间复杂度与正确算法相同，请问它错在哪里？