[AGC037D] Sorting a Grid 题解

题目链接

点击打开链接

题目解法

从后往前推一下，可以得到 \(C\) 一定要把每一行的数都归位到那一行，\(B\) 一定要每一列的目标行数互不相同
考虑构造 \(B\)
这个限制看起来略有些网络流，所以考虑如何建图
令 \(a_{i,j}\) 的目标行数为 \(ln_{i,j}\)，我们由 \(i\to ln_{i,j}\) 连边

不难发现，问题变成了找 \(m\) 组完美匹配
这个问题有一个比较好的解法是：每次随便找一个完美匹配，然后删去边
考虑这样为什么对？根据 \(hall\) 定理，二分图不存在完美匹配的充要条件是存在子集 \(S\) 满足左部点 \(S\) 连到的右部点集合的大小 \(<|S|\)
设当前未匹配的列有 \(k\) 列，左部点集\(|S|\) 与右部点集 \(|T|\) 不合法，因为 \(|S|,|T|\) 之间有 \(k|S|\) 条边，所以 \(|T|\) 中必有点的度数 \(>k\)，矛盾

可以直接跑 \(m\) 次匈牙利
时间复杂度 \(O(mn^3)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=110;
int n,m,a[N][N],ln[N][N],b[N][N],c[N][N];
bool vis[N];
int match[N],G[N][N];
pii t[N];
bool find(int x){
    F(i,1,n) if(!vis[i]&&G[x][i]){
        vis[i]=1;
        if(!match[i]||find(match[i])){ match[i]=x;return true;}
    }
    return false;
}
vector<int> rec[N][N];
int main(){
    read(n),read(m);
    F(i,1,n) F(j,1,m) read(a[i][j]),ln[i][j]=(a[i][j]-1)/m+1;
    F(i,1,n) F(j,1,m) G[i][ln[i][j]]++,rec[i][ln[i][j]].pb(a[i][j]);
    F(j,1,m){
        ms(match,0);
        int res=0;
        F(i,1,n) ms(vis,0),res+=find(i);
        assert(res==n);
        F(i,1,n){
            int x=match[i];
            G[x][i]--,b[x][j]=rec[x][i].back();rec[x][i].pop_back();
        }
    }
    F(i,1,n){ F(j,1,m) printf("%d ",b[i][j]);puts("");}
    F(j,1,m){
        F(i,1,n) t[i]={(b[i][j]-1)/m+1,b[i][j]};
        sort(t+1,t+n+1);
        F(i,2,n) assert(t[i].first!=t[i-1].first);
        F(i,1,n) c[i][j]=t[i].second;
    }
    F(i,1,n){ F(j,1,m) printf("%d ",c[i][j]);puts("");}
    return 0;
}