HDU 5765 Bonds（状压DP）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5765

【题目大意】

　　给出一张图，求每条边在所有边割集中出现的次数。

【题解】

　　利用状压DP，计算不同的连通块，对于每条边，求出两边的联通块的划分方案数，就是对于该点的答案。

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int n,m,T,Cas=1,x[400],y[400],mp[(1<<20)+5],ans,sta[21];

bool g[21][21],dp[(1<<21)+5];

int main(){

    scanf("%d",&T);

    memset(mp,-1,sizeof(mp));

    for(int i=0;i<20;i++)mp[1<<i]=i;

    while(T--){

        scanf("%d%d",&n,&m);

        memset(g,0,sizeof(g));

        memset(sta,0,sizeof(sta));

        for(int i=1;i<=m;i++){

            scanf("%d%d",&x[i],&y[i]);

            if(x[i]<y[i])swap(x[i],y[i]);

            g[x[i]][y[i]]=g[y[i]][x[i]]=1;

            sta[x[i]]|=1<<y[i];

            sta[y[i]]|=1<<x[i];

        }dp[0]=1;

        for(int s=1;s<(1<<n);s++){

            dp[s]=0;

            if(s==(s&-s)){dp[s]=1;continue;}

            for(int x=0;x<n;x++){

                if(s&(1<<x)){if(dp[s^(1<<x)]&&(sta[x]&s)){dp[s]=1;break;}}

            }

        }printf("Case #%d:",Cas++);

        for(int i=1;i<=m;i++){

            ans=0;

            for(int s1=0;s1<(1<<(n-x[i]-1));s1++)

            for(int s2=0;s2<(1<<(x[i]-y[i]-1));s2++)

            for(int s3=0;s3<(1<<y[i]);s3++){

                int s=s3|(s2<<(y[i]+1))|(1<<x[i])|(s1<<(x[i]+1));

                if(dp[s]&&dp[((1<<n)-1)^s])ans++;

            }printf(" %d",ans);

        }puts("");

    }return 0;

}

HDU 5765 Bonds（状压DP）的相关教程结束。