2013-team4/code/steiner-tree

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
int dp[1<<10][52];
int map[MAXN][MAXN];
int v[MAXK]
//总共N个点，map[][]是floyd后的邻接矩阵，v[]存K个特殊点的编号
//mask的第i位对应第i个特殊点
//dp[mask][i]表示包含mask以i为根的树的最小边权和
//复杂度O(2^K*N*N+3^K*N)
void steiner_tree(int N, int K){
    int S=1<<K;
    for (int mask=1; mask<S; mask++)
        for (int i=0; i<N; i++)
            dp[mask][i]=inf;
    for (int i=0; i<K; i++) dp[1<<i][v[i]]=0;
    for (int i=0; i<N; i++) dp[0][i]=0;
    for (int mask=1; mask<S; mask++){
        for (int x=0; x<N; x++)
            for (int sub=(mask-1)&mask; sub; sub=(sub-1)&mask) //枚举mask的所有子集
                dp[mask][x]=min(dp[mask][x], dp[sub][x]+dp[mask^sub][x]);
        for (int x=0; x<N; x++)
            for (int y=0; y<N; y++)
                dp[mask][x]=min(dp[mask][x], dp[mask][y]+map[x][y]);
    }
}
}}}

int dp[1<<10][52];
int map[MAXN][MAXN];
int v[MAXK]
//总共N个点，map[][]是floyd后的邻接矩阵，v[]存K个特殊点的编号
//mask的第i位对应第i个特殊点
//dp[mask][i]表示包含mask以i为根的树的最小边权和
//复杂度O(2^K*N*N+3^K*N)
void steiner_tree(int N, int K){
    int S=1<<K;
    for (int mask=1; mask<S; mask++)
        for (int i=0; i<N; i++)
            dp[mask][i]=inf;
    for (int i=0; i<K; i++) dp[1<<i][v[i]]=0;
    for (int i=0; i<N; i++) dp[0][i]=0;
    for (int mask=1; mask<S; mask++){
        for (int x=0; x<N; x++)
            for (int sub=(mask-1)&mask; sub; sub=(sub-1)&mask) //枚举mask的所有子集
                dp[mask][x]=min(dp[mask][x], dp[sub][x]+dp[mask^sub][x]);
        for (int x=0; x<N; x++)
            for (int y=0; y<N; y++)
                dp[mask][x]=min(dp[mask][x], dp[mask][y]+map[x][y]);
    }
}