HDU 5765 Bonds

比赛时候想了好久，不会。看了官方题解才会......

Bond是极小割边集合，去掉一个Bond之后，只会将原图分成两个连通块。

假设某些点构成的集合为 s（点集中的点进行状压后得到的一个十进制数），那么剩下的点构成的集合为 t=(1<<n)-1-s

如果s是连通的，t也是连通的，那么跨越s、t集合的边的答案就+1（即跨越s、t集合的边构成一个Bond）。 

因此，只需枚举 s 即可。

接下来问题转变成了以下两个问题：

1.如何判断某个点集合是否连通：状压DP预处理。

2.如何让跨越s、t集合的边的答案+1：如果每次遍历所有的边去加答案，时间复杂度爆炸O(m*(1<<n))，因此需要换一种思路：

我们可以计算出所有Bond有几个，然后减去(u,v)不跨越s,t的Bond个数就是(u,v)这条边的答案。

具体看代码吧~~，再贴上官方题解：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

int T,n,m,e[],sum[(<<)+],sz;

int u[],v[];

bool f[(<<)+];

void pre()

{

    for(int i=;i<n;i++) f[<<i]=;

    for(int i=;i<(<<n);i++)

    {

        if(!f[i]) continue;

        int st=; for(int j=;j<n;j++) if(i&(<<j)) st=st|e[j];

        for(int j=;j<n;j++)

        {

            if(i&(<<j)) continue;

            if(st&(<<j)) f[i|(<<j)]=;

        }

    }

}

int main()

{

    scanf("%d",&T); int cas=;

    while(T--)

    {

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

        memset(e,sz=,sizeof e); memset(f,,sizeof f); memset(sum,,sizeof sum);

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

        {

            scanf("%d%d",&u[i],&v[i]);

            e[u[i]]=e[u[i]]|(<<v[i]), e[v[i]]=e[v[i]]|(<<u[i]);

        }

        pre();

        for(int i=;i<(<<n);i++)

        {

            if(f[i]==||f[(<<n)--i]==) continue;

            if(i>(<<n)--i) break;

            sum[i]=; sum[(<<n)--i]=; sz++;

        }

        for(int i=;i<n;i++)

        {

            for(int j=(<<n)-;j>=;j--)

            {

                if((<<i)&j) continue;

                sum[j]=sum[j]+sum[(<<i)|j];

            }

        }

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

        for(int i=;i<m;i++) printf(" %d",sz-sum[(<<u[i])|(<<v[i])]);

        printf("\n");

    }

    return ;

}