UVA 1175 - Ladies' Choice

1175 - Ladies' Choice

链接

　　稳定婚姻问题。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int pref[N][N],order[N][N],Boys[N],Girls[N],cur[N];

 queue<int>q; // 求婚队列

 void Link(int u,int v) {

     int t = Girls[v];

     if (t) {

         Boys[t] = ;

         q.push(t);

     }

     Boys[u] = v;

     Girls[v] = u;

 }

 void solve() {

     int n = read();

     for (int i=; i<=n; ++i) {

         for (int j=; j<=n; ++j)

             pref[i][j] = read(); // 男孩心中第j个喜欢的女孩

         cur[i] = ; // 求婚对象

         Boys[i] = ; // 男孩的

         q.push(i);

     }

     for (int i=; i<=n; ++i) {

         for (int j=; j<=n; ++j) {

             int t = read();

             order[i][t] = j; // 男孩在女孩中的排名

         }

         Girls[i] = ; // 女孩的

     }

     while (!q.empty()) {

         int u = q.front();q.pop();

         int v = pref[u][cur[u]++];

         if (!Girls[v]) Link(u,v);

         else if (order[v][u] < order[v][Girls[v]]) Link(u,v);

         else q.push(u);

     }

     while (!q.empty()) q.pop();

     for (int i=; i<=n; ++i)

         printf("%d\n",Boys[i]);

 }

 int main() {

     int Case = read();

     while (Case--) {

         solve();

         if(Case) puts("");

     }

     return ;

 }