Bonds_牛客博客

题意：给定一张 $n$ 个点 $m$ 条边的无向图。定义割集 $E$ 为去掉 $E$ 中的边后使得图不连通的边集。定义一个 $b o n d$ 为一个极小割集（即 $b o n d$ 中边的任意一个真子集都不是割集）。

对每条边，求它在多少个 $b o n d$ 中.

${n<=10,n-1\le m\le \frac{n*(n-1)}{2}}$

$b o n d$ 会将图分为两个连通块。

对每条边，求它在多少个 $b o n d$ 中= $b o n d$ 的数量-它在多少个被割出来的连通块中

先预处理所有的连通块，状压表示点集，首先每个点就是一个连通块，往连通块内加一个点，如果有边相连，那么还是连通块。

用高维前缀和求出每个点集出现在多少个被割出来的连通块中。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+7,M=5e6,mod=1e9+7;
int e[25],f[maxn],sum[maxn],u[407],v[407],pw[25];
int main() {
	cin.sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int n,m,lim,T,cas;
	pw[0]=1;
	for(int i=1;i<=20;++i) pw[i]=pw[i-1]*2;
	for(cin>>T,cas=1;cas<=T;++cas) {
		cin>>n>>m,lim=pw[n];
		for(int i=0;i<lim;++i) f[i]=sum[i]=0;
		for(int i=0;i<n;++i) e[i]=0,f[pw[i]]=1;
		for(int i=1;i<=m;++i) {
			cin>>u[i]>>v[i];
			e[u[i]]|=pw[v[i]],e[v[i]]|=pw[u[i]];
		}
		for(int s=0;s<lim;++s) {
			if(!f[s]) continue;
			for(int i=0;i<n;++i) if(!(s&pw[i]) && (s&e[i])) f[s|pw[i]]=1;
		}
		int cnt(0);
		for(int s=0;s<lim;++s) {
			if(!f[s]||!f[lim-1-s]) continue;
			if(s>lim-1-s) break;
			sum[s]=1,sum[lim-1-s]=1,++cnt;
		}
		for(int i=0;i<n;++i) 
		for(int s=0;s<lim;++s) if(!(s&pw[i])) sum[s]+=sum[s|pw[i]];
		cout<<"Case #"<<cas<<':';
		for(int i=1;i<=m;++i) cout<<' '<<cnt-sum[pw[u[i]]|pw[v[i]]];
		cout<<'\n';
	}
	return 0;
}