训练指南 UVALive - 3989（稳定婚姻问题)

---

ayout: post

title: 训练指南 UVALive - 3989（稳定婚姻问题）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 二分图匹配

- 图论

- 训练指南

---

Ladies' Choice

UVALive - 3989

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e3+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"bbibibibbbb="<<endl;

int pref[maxn][maxn],order[maxn][maxn],Next[maxn],future_husband[maxn],future_wife[maxn];

queue<int>Q;

void engage(int man,int woman){

    int m=future_husband[woman];

    if(m)future_wife[m]=0,Q.push(m);

    future_wife[man]=woman;

    future_husband[woman]=man;

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int t;

    cin>>t;

    while(t--){

        int n;

        cin>>n;

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

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

                cin>>pref[i][j];

            Next[i]=1;

            future_wife[i]=0;

            Q.push(i);

        }

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

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

                int x;cin>>x;

                order[i][x]=j;

            }

            future_husband[i]=0;

        }

        while(!Q.empty()){

            int man=Q.front();Q.pop();

            int woman=pref[man][Next[man]++];

            if(!future_husband[woman])engage(man,woman);

            else if(order[woman][man]<order[woman][future_husband[woman]])engage(man,woman);

            else Q.push(man);

        }

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

        for(int i=1;i<=n;i++)cout<<future_wife[i]<<endl;

        if(t)cout<<endl;

    }

    return 0;

}