P9792 solution

henryhu2006 · 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);
}