UOJ 41. 矩阵变换

Discription

给出一个 N 行 M 列的矩阵A, 保证满足以下性质:

1.M>N。

2.矩阵中每个数都是 [0,N] 中的自然数。

3.每行中, [1,N] 中每个自然数都恰好出现一次。这意味着每行中 0 恰好出现 M−N 次。

4.每列中，[1,N] 中每个自然数至多出现一次。

现在我们要在每行中选取一个非零数，并把这个数之后的数赋值为这个数。我们希望保持上面的性质4，即每列中，[1,N] 中每个自然数仍然至多出现一次。

Input

第一行一个正整数 T，表示数据组数。

后面包含 T 组数据，各组数据之间无空行。每组数据以两个正整数 N,M 开始，接下来 N 行，每行 M 个用空格隔开的整数，意义如题所述。

Output

对于每组数据输出一行。如果有解，则输出 N 个整数，依次表示每一行取的数是多少。（这应该是一个 1 到 N 的排列）如果无解，则输出任意卖萌表情。

Sample Input

5 10

0 1 0 2 3 0 0 4 0 5

2 0 3 0 0 1 0 5 4 0

4 2 1 0 0 0 3 0 5 0

0 3 0 4 0 5 0 1 2 0

1 0 0 3 2 4 5 0 0 0

5 10

0 1 0 2 3 0 0 4 0 5

2 0 3 0 0 1 0 5 4 0

4 2 1 0 0 0 3 0 5 0

0 3 0 4 0 5 0 1 2 0

1 0 0 3 2 4 5 0 0 0

Sample Output

4 5 3 1 2

5 4 3 1 2

explanation 两组输入数据是相同的。由于结果不唯一，你可以给出任意一组合法答案

Hint

对于 100% 的数据，N<200,M<400,T<50。

不难证明答案是一个排列，所以就相当于一行和一个数匹配，并且要满足：如果某一行i的某个数x在这一行选的数的左边，并且x这个数在和x这个数匹配的行中的位置比x在i中的位置要靠左，那么就是不合法的。

所以就想到了稳定婚姻问题，用每一行去尽量匹配在这一行靠前的位置的数，而如果有冲突的话数要选择在那一行排在靠后位置的行。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int maxn=205;
int T,n,m,V[maxn][maxn],now;
int pos[maxn],M[maxn][maxn];
int H[maxn],W[maxn];
queue<int> q;

inline bool MERRY(int man,int woman){
	if(!H[woman]||V[woman][man]>V[woman][H[woman]]){
		if(H[woman]) q.push(H[woman]);
		H[woman]=man;
		return 1;
	}
	return 0;
}

inline void mate(){
	for(int i=1;i<=n;i++) q.push(i);
	
	int x;
	while(!q.empty()){
		x=q.front(),q.pop();
		if(!MERRY(x,M[x][++pos[x]])) q.push(x);
	}
}

inline void solve(){
	memset(H,0,sizeof(H));
	memset(pos,0,sizeof(pos));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++){
	    	scanf("%d",&now);
	    	if(now) M[i][++pos[i]]=now,V[now][i]=j;
		}
	memset(pos,0,sizeof(pos));
	
	mate();
	
	for(int i=1;i<=n;i++) W[H[i]]=i;
	for(int i=1;i<n;i++) printf("%d ",W[i]);
	printf("%d
",W[n]);
}

int main(){
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}