【AtCoder Grand Contest 037 D】Sorting a Grid | Mrsrz's blog

二分图匹配。

题目大意：

给定一个 $n\times m$ 的矩阵 $A$，其中 $1\sim n\times m$ 每个整数恰出现一次。

你需要执行以下操作：

1. 对 $A$ 的每行中的元素任意调换位置，得到 $B$。
2. 对 $B$ 的每列中的元素任意调换位置，得到 $C$。
3. 对 $C$ 的每行中的元素任意调换位置，得到 $D$。

其中 $D$ 必须满足 $D_{i,j}=(i-1)\times m+j$。

要求找到一组合法的方案，并输出 $B$ 和 $C$。

题解：

考虑每个数在 $D$ 中的所在行。对于 $2$ 操作前后，每列元素的所在行都是 $1\sim n$ 的一个排列。

我们一列一列确定，对每列的元素，其每行都唯一对应另外一行（目标行），且不重复。

容易想到二分图匹配的模型。我们对每列都用二分图匹配来找到对应行即可。

时间复杂度 $O(n^2m^2)$。

必然有解的证明丢虞大链接跑

Code：

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=105;
int n,m,x,B[N][N],lf[N],C[N][N],d[N],f[N];
bool vis[N],e[N][N];
vector<int>vec[N][N];
bool dfs(int v){
    for(int i=1;i<=n;++i)
    if(!vis[i]&&e[v][i]){
        vis[i]=1;
        if(!lf[i]||dfs(lf[i])){
            lf[i]=v;
            return 1;
        }
    }
    return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
        cin>>x,vec[i][(x-1)/m+1].push_back(x);
    }
    for(int i=1;i<=m;++i){
        memset(e,0,sizeof e);
        for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)e[j][k]=!vec[j][k].empty();
        memset(lf,0,sizeof lf);
        for(int j=1;j<=n;++j){
            memset(vis,0,sizeof vis);
            dfs(j);
        }
        for(int j=1;j<=n;++j){
            d[lf[j]]=f[j]=vec[lf[j]][j].back();
            vec[lf[j]][j].pop_back();
        }
        for(int j=1;j<=n;++j)B[j][i]=d[j],C[j][i]=f[j];
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    cout<<B[i][j]<<" \n"[j==m];
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    cout<<C[i][j]<<" \n"[j==m];
    return 0;
}