题解：P17119 [Algo Beat 009 & MROI-R1] Sheepfold

· · 题解

题意简述

矩阵中有红羊、蓝羊和空格。 每头蓝羊可以独立选择保持蓝色或变成红色。 要求最终每行至多有一头红羊， 每列至多有一头蓝羊，求合法变换数量。

解题思路

为每一行和每一列各建立一个点， 共得到 2n 个点。 每头蓝羊在对应行点与列点之间连一条无向边。

给这条边定向时，约定：

这样，每行最终红羊的数量等于行点收到的可变边数量， 再加上该行原有的固定红羊数量； 每列最终蓝羊的数量正好等于列点的入度。

因此每个点最初都能容纳至多一条入边。 固定红羊会占用对应行点的一份容量。 若同一行原本就有两头红羊，答案立即为 0。 否则，该行点的剩余容量为 0，其余点的容量为 1。

问题已经转化为： 给无向图的每条边定向，使每个点的入度不超过自身容量。 定向只影响边所在的连通块， 不同连通块的方案可以独立选择，最后把方案数相乘。

考虑一个连通块。 设点数为 V，边数为 E， 剩余容量为 0 的点数为 K。 每条边定向后恰好贡献一次入度， 而整个连通块最多容纳 V-K 次入度。

连通图满足 E\geq V-1。 若 E>V，总入度已经超过所有点容量之和，必然无解。 所以只需讨论树和基环树。

当 E=V-1 时，连通块是一棵树。 合法定向恰好有一个点的入度为 0，其余点的入度均为 1。 选定入度为 0 的根后， 每条边都只能从父亲指向儿子，方向唯一。

若 K=0，任意点都能作为根，共有 V 种定向。 若 K=1，容量为 0 的点必须作为根，只有一种定向。 若 K\geq2，至少有一个容量为 0 的点不是根，因而无解。

当 E=V 时，连通块是一棵基环树。 此时所有点都必须恰好收到一条入边，所以必须有 K=0。 环可以沿两个方向之一形成有向环。 环外的每条边都只能从靠近环的一端指向远离环的一端， 因此两种环方向分别唯一确定整个连通块，共有两种方案。

用并查集维护蓝羊形成的连通块。 每个根节点同时保存当前点数、边数和容量为 0 的点数。 读到蓝羊时合并两个端点，并把边数增加一； 读到该行第一头固定红羊时， 把它所在连通块的容量为 0 点数增加一。 之后发生合并时，三项统计量一起合并即可。

并查集操作的总时间复杂度为 O((n+m)\alpha(n))， 空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=2005;
const int mod=218105633;
int f[N],siz[N],edge[N],zero[N],used[N];
int find(int x)
{
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
    {
        edge[x]++;
        return;
    }
    if(siz[x]<siz[y])swap(x,y);
    f[y]=x;
    siz[x]+=siz[y];
    edge[x]+=edge[y]+1;
    zero[x]+=zero[y];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n*2;i++)
    {
        f[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        int r,c;
        char x;
        cin>>r>>c>>x;
        if(x=='R')
        {
            if(used[r])
            {
                cout<<0<<'\n';
                return 0;
            }
            used[r]=1;
            zero[find(r)]++;
        }
        else merge(r,n+c);
    }
    ll ans=1;
    for(int i=1;i<=n*2;i++)
    {
        if(find(i)!=i)continue;
        int res=0;
        if(edge[i]==siz[i]&&zero[i]==0)res=2;
        if(edge[i]==siz[i]-1)
        {
            if(zero[i]==0)res=siz[i];
            if(zero[i]==1)res=1;
        }
        ans=ans*res%mod;
    }
    cout<<ans<<'\n';
    return 0;
}