ayout: post
title: 训练指南 UVALive - 3989（稳定婚姻问题）
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 二分图匹配
- 图论
- 训练指南
Ladies' Choice
#include 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="<
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]