[清华集训2015 Day2]矩阵变换-[稳定婚姻模型]

Description

给出一个N行M列的矩阵，保证满足以下性质：

1. M>N。
2. 矩阵中每个数都是 [0,N]中的自然数。
3. 每行中, [1,N]中每个自然数刚好出现一次，其余的都是0。
4. 每列中，[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");

    }

}