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

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

链接

分析：

　　神题！

　　这题可以转化为稳定婚姻问题。每行喜欢出现尽量靠左的数，每个数喜欢它出现位置（这个数在这行中出现的位置）尽量靠右的行。要求每一行匹配一个数，每一个数匹配一行。

　　稳定婚姻问题中不合法的匹配是指：对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。（摘自Matrix67）。

　　可以发现，此题的不合法匹配（一列中出现两个相同的数）与稳定婚姻问题的不合法匹配相似。

　　即在一行中选择一个数是合法匹配，那么这个数在当前位置的右边没有这个数的行（更优的行，保证满足条件），如果一个数选择了一个行，那么其他行的这个数的位置的右边是没有这个数。　　

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9 
10 const int N = 510;
11 int order[N][N],pref[N][N],cur[N],cnt[N],Boys[N],Girls[N];
12 int a[N][N],q[50010],L,R; // q的数据范围！！！ 
13 
14 void Link(int u,int v) {
15     int t = Girls[v];
16     if (t) {
17         Boys[t] = 0;
18         q[++R] = t;
19     }
20     Boys[u] = v;
21     Girls[v] = u;
22 }
23 void solve() {
24     int n = read(),m = read();
25     L = 1,R =  0;
26     memset(Boys,0,sizeof(Boys));
27     memset(Girls,0,sizeof(Girls));
28     memset(cnt,0,sizeof(cnt));
29     for (int i=1; i<=n; ++i) {
30         cur[i] = 1;
31         q[++R] = i;
32         int p = 0;
33         for (int j=1; j<=m; ++j) {    
34             a[i][j] = read();
35             if (a[i][j]) pref[i][++p] = j;
36         }
37     }
38     for (int j=m; j>=1; --j) {
39         for (int i=1; i<=n; ++i) {
40             if (a[i][j]) order[a[i][j]][i] = ++cnt[a[i][j]];
41         }
42     }
43     while (L <= R) {
44         int u = q[L++];
45         int v = a[u][pref[u][cur[u]++]];
46         if (!Girls[v]) Link(u,v);
47         else if (order[v][u] < order[v][Girls[v]]) Link(u,v);
48         else q[++R] = u;
49     }
50     for (int i=1; i<=n; ++i) 
51         printf("%d ",Boys[i]);
52     puts("");
53 }
54 int main() {
55     int Case = read();
56     while (Case--) solve();    
57     return 0;
58 }