[清华集训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");
} }
上一篇:jquery概要--基础02


下一篇:IDEA(添加类注释以及方法注释)