Wuyanru's blog
0%

[SNOI2024] 拉丁方

发表于 分类于 ，

场上只会 分，太不牛了！

题目链接

题意

称一个 的方阵是合法的，当且仅当这个方阵的每一行和每一列都是一个 的排列。

给定一个方阵的左上角 区域，构造一个合法方阵或判断无解。

。

组数据。

给定区域数字每行每列互不相同，且都在 内。

题解

考虑 时怎么做。

建出一个二分图，左边 个点表示方阵的 个列，右边 个点表示 种数字。

左边第 个点向右边第 个点连边，当且仅当第 列还没有填 。

显然，这个二分图共有 条边。

那么有解当且仅当我们可以求出 组不相交的完美匹配（一组完美匹配对应其中一行的填法）。

根据 Hall 定理，我们一定可以先求出一组完美匹配，这样就可以令 ，继续做即可。

同时也说明 一定有解。

对于 的情况，考虑先把前 行的右边填好，然后做 时的部分。

我们首先设 表示颜色 在左上角区域的出现次数。

因为前 行颜色 一定出现了 次，所以右上角颜色 一定出现了 次。

所以一定有 ，否则无解。

还是建出一个二分图，左边 个点表示 个行，右边 个点表示 种数字。

这个二分图不太一样，共有 条边，左边点度数均为 ，右边点度数 。

所以在 的时候根据 Hall 定理也一定能做。

这样我们就可以在略大的复杂度内进行构造。

单次使用网络流匹配复杂度为 ，所以总时间复杂度是 。

发现复杂度瓶颈在于求 次完美匹配。

可以使用 CF600F 的二分图边染色或者 正则二分图匹配 将复杂度变为 或 。

特别地，若使用正则二分图匹配，需要在 的部分额外补 个左部点。

代码

我写的是 的二分图边染色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int col[1001][1001];
int nod[1001][501];
int a[501][501];
bool vis[501];
int cnt[501];
int n,r,c;
inline void clear()
{
    memset(col,0,sizeof(col));
    memset(nod,0,sizeof(nod));
}
inline int get(int id)
{
    for(int i=1;;i++) if(!nod[id][i]) return i;
}
inline void add(int u,int v,int c1,int c2)
{
    if(nod[v][c1])
    {
        int w=nod[v][c1];
        nod[v][c1]=nod[w][c1]=0;
        col[v][w]=col[w][v]=0;
        add(v,w,c2,c1);
    }
    nod[v][c1]=u,nod[u][c1]=v;
    col[u][v]=col[v][u]=c1;
}
inline void add(int u,int v)
{
    int c1=get(u),c2=get(v);
    add(u,v,c1,c2);
}
inline void solve()
{
    memset(cnt,0,sizeof(cnt));
    n=read(),r=read(),c=read();
    for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) cnt[a[i][j]=read()]++;
    for(int i=1;i<=n;i++) if(cnt[i]+n-c<r)
    {
        printf("No\n");
        return ;
    }
    printf("Yes\n");
    //part 1
    clear();
    for(int i=1;i<=r;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=c;j++) vis[a[i][j]]=1;
        for(int j=1;j<=n;j++) if(!vis[j]) add(i,j+n);
    }
    for(int i=1;i<=r;i++) for(int j=1;j<=n;j++) if(col[i][j+n]) a[i][col[i][j+n]+c]=j;
    //part 2
    clear();
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=r;j++) vis[a[j][i]]=1;
        for(int j=1;j<=n;j++) if(!vis[j]) add(i,j+n);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(col[i][j+n]) a[col[i][j+n]+r][i]=j;

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",a[i][j]," \n"[j==n]);
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}

感谢观看！