正文开始

阅读理解：

有一个

N

行

M

列的图，其中有数值为

1∼N

的数各

M

个。你可以对每一行进行任意排列，能否在每一列中数值为

1∼N

的数各出现一次？输出方案。

思路：

可以发现，这道题是必定能完成目标的，因为当有

M

列时，你一定可以凑出一列数值为

1∼N

的数各出现一次，删掉这一列后，剩余的矩阵依旧满足题目所述条件，所以可以重复上面操作，以此类推。

方案如何处理呢？我们可以每次处理当前的首列，将这一列的每一排当作二分图的左边一部分，然后将每一排剩下还可以选的数字与其对应的排相连，然后跑一个二分图最大匹配即可，最后统计答案。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5;
int n,m,e;
int a[N][N],v[N][N];
int b[N],li[N],ans[N][N];
inline bool find(int u){
	for(int i=1;i<=n;i++)
		if(v[u][i]>0&&!b[i]){
			b[i]=1;
			if(!li[i]||find(li[i])){li[i]=u;return 1;}
		}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin>>a[i][j],v[i][a[i][j]]++;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){memset(b,0,sizeof(b)),find(j);}//跑二分图最大匹配 
		for(int j=1;j<=n;j++)ans[li[j]][i]=j,v[li[j]][j]--,li[j]=0;//统计答案 
	}
	cout<<"Yes\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cout<<ans[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}

题解：AT_abc317_g [ABC317G] Rearranging

文章操作

正文开始

阅读理解：

思路：

代码

相关推荐

评论

题解：AT_abc317_g [ABC317G] Rearranging