HDU 4085 Peach Blossom Spring（斯坦纳树）

雨点打透心脏的1/2处 2021-11-23 10:04 226阅读 0赞

## 题意：k个房子k个庇护所,每一座房子都必须可以和一个庇护所联通.。 ##

## 分析：斯坦纳森林模板题，不是所有要求点都连通，题目就是要求斯坦纳森林，由于上述限制条件，合法的状态必须是房子数量和庇护所数量相同，最终树合并成森林时对状态判断一下合法性就行了。 ##

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> pii;
    #define fi first
    #define se second
    #define mp make_pair
    #define pb push_back
    const int maxn=65;
    const int maxm=1<<10;
    const int maxe=2015;
    const int inf=0x3f3f3f3f;
    int n,m,k,nn;
    struct edge
    {
        int to,nxt,len;
    } e[maxe];
    int head[maxn],tot;
    void adde(int u,int v,int l)
    {
        e[tot].to=v;
        e[tot].len=l;
        e[tot].nxt=head[u];
        head[u]=tot++;
    }
    
    int d[maxn][maxm];
    int dp[maxm];
    int s[maxn];
    
    void init()
    {
        tot=0;
        memset(head,-1,sizeof(head));
        memset(s,0,sizeof(s));
        scanf("%d%d%d",&n,&m,&k);
        nn=1<<(2*k);
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<nn; j++)d[i][j]=inf;
        }
        int a,b,c;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            adde(a,b,c);
            adde(b,a,c);
        }
        for(int i=1; i<=k; i++)
        {
            s[i]=1<<(i-1);
            d[i][s[i]]=0;
            s[n-i+1]=1<<(k+i-1);
            d[n-i+1][s[n-i+1]]=0;
        }
    }
    
    queue<pii> que;
    bool inque[maxn][maxm];
    
    ///check函数判断合法状态（对应点对（集）是否连通）
    inline bool check(int msk)
    {
        ///只有人的个数和房子的个数相等的时候才算合法状态
        int v1=0,v2=0;
        for(int i=0; i<k; i++)if(msk>>i&1)v1++;
        for(int i=k; i<2*k; i++)if(msk>>i&1)v2++;
        return v1==v2;
    }
    
    inline bool update(int x,int y,int w)
    {
        if(w<d[x][y])
        {
            d[x][y]=w;
            return 1;
        }
        return 0;
    }
    
    ///SPFA进行松弛
    void spfa()
    {
        while(!que.empty())
        {
            int x=que.front().fi,y=que.front().se;
            que.pop();
            for(int i=head[x]; i!=-1; i=e[i].nxt)
            {
                int v=e[i].to,w=e[i].len;
                ///只需要对当前层的节点进行spfa就行了，不需要整个图完全松弛一遍，
                ///因为更高的层都可以通过枚举子集而变成若干个更低的层
                if(update(v,y|s[v],d[x][y]+w)&&y==(y|s[v])&&!inque[v][y])
                {
                    inque[v][y]=1;
                    que.push(mp(v,y));
                }
            }
            inque[x][y]=0;
        }
    }
    
    /// 斯坦纳树核心代码（状压dp）
    void work()
    {
        for(int msk=0; msk<nn; msk++)
        {
            for(int x=1; x<=n; x++)
            {
                /// 第一重，先通过连通状态的子集进行转移。
                /// dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] }
                for(int i=(msk-1)&msk; i; i=(i-1)&msk)
                {
                    d[x][msk]=min(d[x][msk],d[x][i|s[x]]+d[x][(msk-i)|s[x]]);
                }
                if(d[x][msk]<inf)
                {
                    que.push(mp(x,msk));
                    inque[x][msk]=1;
                }
            }
            /// 第二重，在当前枚举的连通状态下，对该连通状态进行松弛操作。
    		/// dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }
            spfa();
        }
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            init();
            work();
            ///2k个点都连通时的答案
            for(int j=1; j<nn; j++)
            {
                dp[j]=inf;
                for(int i=1; i<=n; i++)dp[j]=min(dp[j],d[i][j]);
            }
            ///合并子集 考虑不合法的状态
            for(int i=1; i<nn; i++)
            {
                if(check(i))
                {
                    for(int j=(i-1)&i; j; j=(j-1)&i)
                    {
                        if(check(j))
                        {
                            dp[i]=min(dp[i],dp[j]+dp[i-j]);
                        }
                    }
                }
            }
            if(dp[nn-1]>=inf)printf("No solution\n");
            else printf("%d\n",dp[nn-1]);
        }
        return 0;
    }