P10062 [SNOI2024] 拉丁方题解

LRC0511 · 2024-01-18 19:03:49 · 题解

提供一个好写的做法。

首先考虑 R=n 时怎么做，此时我们可以确定所有行剩余部分可以填的数的集合，我们只需保证每一列的数不重复就够了。

我们将每一行作为左部点，每种数作为右部点，如果该行可以填某个数则连一条边，这是一张二分图，且每个点的度数均为 n-C。

根据上面的讨论，我们需要将其划分成 n-C 组完美匹配，每一组匹配确定了每一列填哪些数。

我们知道，一张二分图的边染色数是它每个点度数的最大值。因此我们可以求出这张图的一个 n-C 边染色，对于每种颜色的所有边，易知它们构成了一组完美匹配。

只需要利用 CF600F 的方法求一次二分图边染色即可，时间复杂度 O(n^3)。

再考虑 R \neq n 的情况。我们考虑先填左下角的部分，将问题转化为 R=n 的情况。

同样可以确定前 C 列可填的数的集合，利用同样的方式建图，我们得到了一张左部点度数均为 n-R 的二分图。

如果某个右部点的度数大于 n-R，这意味着某个数出现的次数超过 n-R，但是未填的 n-R 行中，每行至多填一个，因此此时必然无解。

所以该二分图有 n-R 边染色，每种颜色的边对应一组左部满的匹配，对应每一行所填的数的集合。

只需再跑一次二分图边染色即可，时间复杂度 O(n^3)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,r,c,a[N][N],to[N*2][N];
namespace Paint
{
    inline void init(int n,int d)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=d;j++)
                to[i][j]=0;
    }
    void dfs(int u,int v,int x,int y)//x->y
    {
        if(!to[v][y]){to[u][y]=v,to[v][y]=u,to[v][x]=0;return;}
        int w=to[v][y];
        if(to[w][x]) dfs(w,to[w][x],x,y);
        else to[w][y]=0;
        to[w][x]=v,to[v][x]=w,to[v][y]=u,to[u][y]=v;
    }
    inline void add(int u,int v)
    {
        int x=1,y=1;while(to[u][x]) x++;
        while(to[v][y]) y++;
        if(x==y){to[u][x]=v,to[v][y]=u;return;}
        dfs(u,v,y,x);
    }
}
int tmp[N];
bool work1()
{
    for(int i=1;i<=n;i++) tmp[i]=c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            tmp[a[i][j]]--;
    for(int i=1;i<=n;i++)
        if(tmp[i]>n-r) return 0;
    Paint::init(n+c,n-r);
    for(int j=1;j<=c;j++)
    {
        for(int i=1;i<=n;i++) tmp[i]=0;
        for(int i=1;i<=r;i++) tmp[a[i][j]]=1;
        for(int i=1;i<=n;i++)
            if(!tmp[i]) Paint::add(j,c+i);
    }
    for(int j=1;j<=c;j++)
        for(int i=r+1;i<=n;i++)
            a[i][j]=to[j][i-r]-c;
    return 1;
}
void work2()
{
    Paint::init(2*n,n-c);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) tmp[j]=0;
        for(int j=1;j<=c;j++) tmp[a[i][j]]=1;
        for(int j=1;j<=n;j++)
            if(!tmp[j]) Paint::add(i,n+j);
    }
    for(int i=1;i<=n;i++)
        for(int j=c+1;j<=n;j++)
            a[i][j]=to[i][j-c]-n;
}
void work()
{
    cin>>n>>r>>c;bool fl=1;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>a[i][j];
    if(r<n) fl=work1();
    if(fl) work2();
    if(!fl){cout<<"No\n";return;}
    cout<<"Yes\n";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" \n"[j==n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;while(T--) work();
    return 0;
}

P10062 [SNOI2024] 拉丁方 题解

P10062 [SNOI2024] 拉丁方题解