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
|
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 (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; }
|
近期评论