HDU5765 Bonds 最小割极

http://acm.hdu.edu.cn/showproblem.php?pid=5765

题意：无向连通图，问每条边在几个最小割极上

思路：用位压形式，表示边的关系。g[1<<i]=1<<x 表示第i个点与哪几个点相连。然后，处理出每种点集和哪些点相连。每个点构成一个连通图，所以枚举当前点集，可以得到所有连通图的点集，计算出数量，用高维前缀和处理所有包含i点的连通块

ans=(所有连通块-同时包含(i,j)的连通块数目)/2 应为以(i,j)为割边的连通块，删除该边以后，数量加倍，所以除2

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdlib>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<vector>

 #include<cstring>

 #include<stack>

 #include<cmath>

 #include<queue>

 #include <conio.h>

 #define clc(a,b) memset(a,b,sizeof(a))

 #include <bits/stdc++.h>

 const int maxn = ;

 const int inf=0x3f3f3f3f;

 const double pi=acos(-);

 typedef long long LL;

 using namespace std;

 //const LL MOD = 1e9+7;

 void fre(){freopen("in.txt","r",stdin);}

 inline int lb(int x){return x&(-x);}

 const int N=<<;

 int g[N],a[N],u[],v[];

 bool vis[N];

 int sum[N];

 int main(){

     int T;

     scanf("%d",&T);

     for(int cas=;cas<=T;cas++){

         int n,m;

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

         for(int i=;i<<<n;i++) sum[i]=,g[i]=,vis[i]=false;

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

             int x,y;

             scanf("%d%d",&x,&y);

             u[i]=x,v[i]=y;

             g[<<x]|=<<y;

             g[<<y]|=<<x;

         }

         for(int i=;i<<<n;i++) g[i]|=g[i-lb(i)]|g[lb(i)];

         int l=,r=;

         for(int i=;i<n;i++) vis[a[r++]=<<i]=true;

         while(l<r){

            int c=a[l++];

            int res=g[c]^(g[c]&c);

            while(res){

              int tem=lb(res)|c;

              if(!vis[tem]) vis[a[r++]=tem]=true;

              res-=lb(res);

            }

         }

         int all=;

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

             int j=(<<n)-;

             j^=i;

             if(vis[i]&&vis[j]){

                 sum[i]++,sum[j]++,all++;

             }

         }

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

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

                 if(!(i&(<<j))) sum[i]+=sum[i^(<<j)];

         }

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

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

             printf("%d",(all-sum[(<<u[i])|(<<v[i])])/);

             if(i==m-) cout<<endl;

             else cout<<" ";

         }

     }

     return ;

 }