自动搬运

查看原文

来自洛谷，原作者为

	henryhu2006 **

搬运于2025-08-24 22:51:53，当前版本为作者最后更新于2024-02-06 20:03:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

二分图匹配，但是一个左部点要恰好匹配两个右部点，求最大匹配。

多测，$\sum (n+m)\le 150$。

建图

将左部点（男）拆点成 $x,x'$，对于一条边 $(x,y)$，$(x,y)$ 和 $(x',y)$ 都连边，并连接 $(x,x')$。答案即为一般图最大匹配 $-n$。

证明是容易的。如果一个左部点没有匹配成组，则 $(x,x')$ 必然匹配；如果一个左部点匹配成组，那么一定处于两对匹配，且两个 $y$ 不同。

一般图最大匹配

带花树是不好的。由于此题只需要求最大匹配的大小，无需构造方案，且 $n+m$ 不是很大，我们可以使用 Tutte 矩阵 来做。

以下参考 OI-Wiki。

具体来讲，对于每条边有个变量，设为 $x_{u,v}$。Tutte 矩阵是 $n\times n$ 的。

• 对于位置 $(i,j)$，$i<j$，如果存在边 $(i,j)$，则值为 $x_{i,j}$。
• 对于位置 $(j,i)$，$i<j$，如果存在边 $(i,j)$，则值为 $-x_{i,j}$。
• 否则为 $0$。

这个矩阵的秩是偶数，且最大匹配即为秩的一半。

变量不好处理，可以每个变量随机权值，可以证明错误率 $<\dfrac{n}{p}$，其中 $n$ 为点数，$p$ 为大质数，取 $10^9+7$ 即可。

于是直接高斯消元。

int T,n,m,a[N][N];
mt19937_64 rnd(time(0));
char s[N];
void add(int u,int v){
	int w=rnd()%mod;
	a[u][v]=w,a[v][u]=mod-w;
}
int chk(int x){
	if(x>=mod) x-=mod; return x;
}
void solve(){
	memset(a,0,sizeof(a)),cin>>n>>m;
	for(int i=1;i<=n;++i) add(i,n+i);
	for(int i=1;i<=n;++i){
		scanf("%s",s+1);
		for(int j=1;j<=m;++j)
			if(s[j]=='1') add(i,2*n+j),add(i+n,2*n+j);
	}
	int res=0; m+=2*n;
	for(int i=1;i<=m;++i){
		if(!a[i][i]){
			int r=0;
			for(int j=i+1;j<=m;++j)
				if(a[j][i]){r=j; break;}
			if(!r) continue;
			swap(a[i],a[r]);
		}
		++res;
		for(int j=i+1;j<=m;++j){
			int v=1ll*a[j][i]*ksm(a[i][i],mod-2)%mod;
			for(int k=i;k<=m;++k)
				a[j][k]=chk(a[j][k]-1ll*v*a[i][k]%mod+mod); 
		}
	}
	printf("%d\n",res/2-n);
}