Fork me on GitHub

Uoj#41.【清华集训2014】矩阵变换

Uoj#41. 【清华集训2014】矩阵变换

题意:

  • ​题面给的非常简单不易懂。

题解:

  • 听说这是一道稳定婚姻模板题。
  • 把行看作男的,把数看作女的。
  • 行喜欢靠前的数,数喜欢出现靠后的行。
  • 我们发现如果答案不满足条件,那么必有一个数在某列出现了两次。
  • 可以发现这并不满足稳定婚姻的要求。
  • 复杂度$O(nm)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef pair<int,int> pii;
const int N=409;
int n,m,number[N],cnt;
int a[N][N],b[N][N],c[N][N],nxt[N],fh[N],fw[N];
queue<int> q;
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
void engage(int x,int y)
{
int last=fh[y];
if (last)
{
fw[last]=0;
q.push(last);
}
fw[x]=y;
fh[y]=x;
}
int main()
{
int T=read();
while (T--)
{
n=read(),m=read();
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++) number[i]=0;
for (int i=1;i<=n;i++)
{
cnt=0;
for (int j=1;j<=m;j++)
{
int x=read();
if (x)
{
a[x][j]=i;
b[i][++cnt]=x;
}
}
}
for (int i=1;i<=n;i++)
{
cnt=0;
reverse(a[i]+1,a[i]+m+1);
for (int j=1;j<=m;j++)
if (a[i][j]) a[i][++cnt]=a[i][j];
}
for (int i=1;i<=n;i++)
nxt[i]=1,fw[i]=0,q.push(i);
for (int i=1;i<=n;i++)
{
fh[i]=0;
for (int j=1;j<=n;j++) c[i][b[i][j]]=j;
}
while (!q.empty())
{
int x=q.front();
q.pop();
int y=a[x][nxt[x]++];
if (!fh[y]) engage(x,y);
else if (c[y][x]<c[y][fh[y]]) engage(x,y);
else q.push(x);
}
for (int i=1;i<=n;i++)
printf("%d%s",fh[i],i==n?"\n":" ");
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#41.【清华集训2014】矩阵变换

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj41/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。