传送门

给出一张无向图,问在所有最小割中,每条边出现多少次。

---

首先最小割准确无误的把图分为两个连通块

那么我们可以枚举连通块的所有状态

那么剩下的点集也必然是一个连通块

如何判断一个状态是否是一个连通块呢???

我们可以使用并查集,在 O ( m 2 n ) O(m2^n) O(m2n)的时间内完成判断,这显然不可取

不过我们可以用状压 d p dp dp,设 f [ u ] f[u] f[u]为点击状态为 u u u时是否可能连通

f [ u ]   ∣ = f [ v ] f[u]\ |= f[v] f[u] ∣=f[v]当且仅当存在边 ( u , v ) (u,v) (u,v)

现在枚举了这两个连通块,显然连通块之间的边都应该被切掉，都是割边

此时可以 O ( m ) O(m) O(m)暴力枚举每条边,但是这样又超时了hhh,需要换一种思路

这里有两种相近的思路

Ⅰ . 正 难 则 反 \color{Red}Ⅰ.正难则反 Ⅰ.正难则反

不妨先求每条边不在割集中的次数

也就是对于边 ( u , v ) (u,v) (u,v)出现在连通块中的次数

边的状态压缩成 w = ( 1 < < ( u − 1 ) ) ∣ ( 1 < < ( v − 1 ) ) w=(1<<(u-1))|(1<<(v-1)) w=(1<<(u−1))∣(1<<(v−1)),设连通块状态为 s t a t e 1 , s t a t e 2 state1,state2 state1,state2

令 f [ s t a t e 1 ] + + , f [ s t a t e 2 ] + + f[state1]++,f[state2]++ f[state1]++,f[state2]++,那么边 w w w的所有超集累加值就是次数

做一遍 S O S D P SOSDP SOSDP即可,最后除以二因为连通块的次数正反都被算了

Ⅱ . 直 接 求 \color{Red}Ⅱ.直接求 Ⅱ.直接求

考虑直接求 ( u , v ) (u,v) (u,v)在割集中出现的次数

把 f [ s t a t e 1 ] − − , f [ s t a t e 2 ] − − , f [ s t a t e 1 ∣ s t a t e 2 ] + + f[state1]--,f[state2]--,f[state1|state2]++ f[state1]−−,f[state2]−−,f[state1∣state2]++即可

因为跨越 s t a t e 1 , s t a t e 2 state1,state2 state1,state2的边只会增加,在连通块里面的就会抵消

还是和上面一样做 S O S D P SOSDP SOSDP求超集和

#include <bits/stdc++.h>
using namespace std;
int f[1<<21],dp[1<<21],l[3000],r[3000],sta[30],t,n,m,casenum;
int main()
{
	cin >> t;
	while( cin >> n >> m )
	{
		for(int i=1;i<=m;i++)
		{
			cin >> l[i] >> r[i];
			sta[l[i]] |= (1<<r[i]);
			sta[r[i]] |= (1<<l[i]);
		}
		int mx = 1<<n;
		for(int i=0;i<n;i++)	dp[1<<i] = 1;
		dp[0] = 1;
		for(int i=0;i<mx;i++)
		{
			for(int j=0;j<n;j++)
			{
				if( (i&(1<<j))==0 )	continue;
				if( sta[j]&(i^(1<<j)) )	dp[i] |= dp[i^(1<<j)];
			}
		}
		int sum = 0;
		for(int i=1;i<mx-1;i++)//枚举连通块 
		{
			if( dp[i]&&dp[(mx-1)^i] )//都是连通块
				f[i]++,f[(mx-1)^i]++,sum++; 
		}
		for(int i=0;i<n;i++)
		for(int j=mx-1;j>=0;j--)
			if( (j&(1<<i))==0 )	f[j] += f[j|(1<<i)];
		printf("Case #%d: ",++casenum);
		for(int i=1;i<=m;i++)
			printf("%d%c",(sum-f[ (1<<l[i]) | (1<<r[i]) ] )/2," \n"[i==m] );
		for(int i=0;i<n;i++)	sta[i] = 0;
		for(int i=0;i<mx;i++)	f[i] = dp[i] = 0;
	}
}