Description
给出一个N行M列的矩阵，保证满足以下性质：
- M>N。
- 矩阵中每个数都是 [0,N]中的自然数。
- 每行中, [1,N]中每个自然数刚好出现一次，其余的都是0。
- 每列中，[1,N]中每个自然数最多出现一次。
现在我们要在每行中选取一个非零数，并把这个数之后的数赋值为这个数。我们希望保持上面的性质4，即每列中，[1,N]中每个自然数仍最多出现一次。
对于 100% 的数据，N<200,M<400,T<50。
Solution
稳定婚姻模型。
把行当成男孩，数字当成女孩。男孩喜欢在他自己那行靠前的女孩，女孩喜欢她自己所出现位置靠右的行。
则，假如婚姻不稳定(婚姻不稳定是指同时1男1女喜欢对方超过自己的伴侣)：
. . . . y . . . x .
. y . . . . . . . .
如图，假设行1匹配x，行2匹配y。此时，男孩1更喜欢女孩y，女孩y更喜欢男孩1，这两位就会私奔啦。此种情况下，赋值完毕后：
| . | . | . | . | y | . | . | . | x | x |
| . | y | y | y | y | y | y | y | y | y |
很显然这就不合法了。
同样，任何不合法局面都不可能使婚姻稳定。（证毕）
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=,M=;
int T,n,m;
int a[N][M],b[N][M],rkg[N][M];
queue<int>q;
int cnt[N];
int d[N];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (int i=,now=;i<=n;i++,now=) for (int j=;j<=m;j++)
{scanf("%d",&a[i][j]);if (a[i][j]) b[i][++now]=a[i][j],rkg[a[i][j]][i]=j;}
for (int i=;i<=n;i++) q.push(i),cnt[i]=;
int x,v;
memset(d,,sizeof(d));
while (!q.empty())
{
x=q.front();q.pop();
v=b[x][cnt[x]];
if (d[v]&&rkg[v][x]<rkg[v][d[v]]){cnt[x]++;q.push(x);}
else
{if (d[v]) q.push(d[v]);d[v]=x;}
}
for (int i=;i<=n;i++) printf("%d ",b[i][cnt[i]]);
printf("\n");
} }