Liveddd's Blog

愛にできることはまだあるかい

[AGC037D] Sorting a Grid

发表于 分类于
本文字数： 3.7k 阅读时长 ≈ 8 分钟

感觉比较普通。

考虑对结尾状态的每行染上相同颜色，那么问题变为对于每一行的数随意交换，使得对于每一列 $m$ 种颜色各出现一次。

我们直接对于每一列分别构造。对于每一列建点，视为左部；对于每种颜色建点，视为右部。二者对应的连边，每次二分图匹配即可得到一列的答案。于是做 $m$ 次最大流即可。使用 Dinic 求解，时间复杂度为 $\mathcal O(n^2 m\sqrt {m})$。

如何保证始终有完美匹配？如果还剩下 $k$ 列未匹配，那么图中每个点的度数都为 $k$，这张图是一张 $k$-正则二分图，选出一组完美匹配即可得到 一张 $k-1$-正则二分图，所以必定存在完美匹配。或者直接根据 Hall 定理得到该结论。

Code
 
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
const int N=3e2+10,M=1e5+10;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n,m;
int a[N][N],b[N][N],c[N][N];
vector<int>vec[N][N];
inline int col(int x){return (x-1)/m+1;}

namespace Flow
{
    int n,s,t;
    int tot=1,head[N],ver[M<<1],e[M<<1],ne[M<<1];
    int d[N],now[N];
    queue<int>q;
    inline void add_edge(int u,int v,int w)
    {
        ver[++tot]=v;
        e[tot]=w;
        ne[tot]=head[u];
        head[u]=tot;
    }
    inline void add(int u,int v,int w){add_edge(u,v,w),add_edge(v,u,0);}
    inline bool BFS()
    {
        while(!q.empty())q.pop();
        memset(d,0,sizeof(d));
        d[s]=1,now[s]=head[s];
        q.push(s);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=ne[i])
            {
                int y=ver[i];
                if(d[y]||!e[i])continue;
                d[y]=d[x]+1,now[y]=head[y];
                if(y==t)return 1;
                q.push(y);
            }
        }
        return 0;
    }
    int Dinic(int x,int flow)
    {
        if(x==t)return flow;
        int res=flow;
        for(int i=now[x];i&&res;i=ne[i])
        {
            now[x]=i;
            int y=ver[i];
            if(d[y]==d[x]+1&&e[i])
            {
                int k=Dinic(y,min(res,e[i]));
                e[i]-=k,e[i^1]+=k;
                res-=k;
            }
        }
        return flow-res;
    }
    void init()
    {
        n=::n;
        s=(n<<1)+1,t=s+1,tot=1;
    }
    void solve()
    {
        for(int i=1;i<=n;i++)add(s,i,1),add(i+n,t,1);
        while(BFS())while(Dinic(s,N));
    }
}


int main()
{
    read(n,m);
    Flow::init();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)read(a[i][j]),Flow::add(i,col(a[i][j])+n,1),vec[i][col(a[i][j])].push_back(j);

    for(int t=1;t<=m;t++)
    {
        using namespace Flow;
        solve();
        for(int x=::n+1;x<=(::n<<1);x++)
            for(int i=head[x];i;i=ne[i])
            {
                if(!e[i])continue;
                int y=ver[i];
                e[i]=0;
                b[y][t]=vec[y][x-(::n)].back();
                vec[y][x-(::n)].pop_back();
            }
    }
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            printf("%d ",c[j][i]=a[i][b[i][j]]);
    for(int i=1;i<=m;i++)sort(c[i]+1,c[i]+1+n);
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            printf("%d ",c[j][i]);
    return 0;
}