题目链接点这里
这题做了好久，，看了网上的题解也看不太懂，，只知道用高维前缀做，，，，，，然后在拉粑粑的时候，，突然想出了一种方法
他是要算出每条边出现在多少割集中，，，我们可以反着想，，我们可以先算出有多少割集（个数设为sum），在算出这条边包含多少合法联通块中（个数设为x），，然后sum-x就是该条边在多少割集中，，
那怎么算有多少个联通快中有这条边那。。。
假设这条的两端是u和v,,,那转化为二进制就是第u位和第v位1，，，，也就是说，，一个用二进制表示的联通快的第u位和第v位为1的话，，就说明该联通快包含这条边，，然后我们就是求，包含u，v这两个二进制位的集合有多少个，，，这不就是高维前缀和所求的吗。
#include<algorithm> #include<iostream> #include<cstring> #include<queue> #include<cmath> #include<cstdio> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) #define FIN freopen("input.txt","r",stdin) #define fuck(x) cout<<x<<endl const int MX=21; #define INF 0x3f3f3f3f #define lson l,m,rt<<1 typedef long long LL; #define rson m+1,r,rt<<1|1 int n,m; int G[MX]; int dp[1<<MX],pre[1<<MX]; int w[MX*MX][2]; int main() { FIN; int T; cin>>T; int cas=0; while(T--) { printf("Case #%d: ",++cas); mem(G,0); scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); G[u]|=(1<<v); G[v]|=(1<<u); w[i][0]=u; w[i][1]=v; } int sum=0;//总共有几个合法的割 dp[0]=dp[(1<<n)-1]=0; pre[0]=pre[(1<<n)-1]=0; for(int i=1; i<(1<<n)-1; i++)//判断子集的联通性 { int flag=0; if((-i&i)^i)//可以使用树状数组的lowbit，来快速求出二进制位是否只有一个1 { for(int j=0; j<n; j++)if((i&(1<<j))&&dp[i^(1<<j)]&&(i&G[j])) { flag=1; break; } } else flag=1; dp[i]=flag; } for(int i=1; i<(1<<n)-1; i++)//有几个合法的割 { pre[i]=dp[i]&dp[(~i)&((1<<n)-1)]; sum+=pre[i]; } for(int i=0; i<n; i++)//高维前缀和 for(int j=(1<<n)-1; j>=1; j--) if(~j&(1<<i)) pre[j]+=pre[j^(1<<i)]; for(int i=1; i<=m; i++)printf("%d%c",sum/2-pre[(1<<w[i][0])|(1<<w[i][1])],i==m?'\n':' '); } return 0; }
