LA 3989 Ladies' Choice (결혼 안정 문제)

문제: n 명의 남자 와 n 명의 여자 가 짝 을 이 루 고 모든 사람 이 마침 파트너 가 있다.존재 하지 않 는 다 면 남자 u 와 여자 v 는 짝 이 없 는데 그들 이 상대방 을 좋아 하 는 정 도 는 각자 의 현재 파트너 정도 보다 크다.
Gale - Shapley 알고리즘 단계:
1. 아직 어 울 리 지 않 은 모든 남자 들 은 그 가 초대 하지 않 은 여자 중에서 자신 이 가장 좋아 하 는 것 을 선택한다.
2. 초 대 받 은 여자 가 파트너 가 없 으 면 초 대 를 받는다.만약 에 파트너 가 있다 면 현재 파트너 와 이 남자 의 순 위 를 비교 하고 현재 파트너 의 순위 가 비교적 낮 으 면 버 리 고 현재 의 초 대 를 받 아들 이 며 반대로 초 대 를 거절 합 니 다.
3. 이 라운드 에서 남자 가 파트너 를 찾 지 못 하면 일치 하지 않 는 팀 에 다시 가입 합 니 다.
알고리즘 정확성 증명:
  상기 알고리즘 을 분석 하면 우 리 는 두 가지 현상 을 발견 할 수 있다. 1. 여 자 는 첫 번 째 청혼 을 받 았 을 때 부터 데이트 상 태 를 유지 하고 그녀 가 데이트 하 는 대상 이 점점 좋아 질 것 이다 (그녀의 순위 표를 보면).2. 남자 가 청혼 하 는 상대 (여자) 는 점점 나 빠 집 니 다!
다음 에 우 리 는 이 알고리즘 의 정확성 에 대해 다음 과 같이 증명 한다. 1. 알고리즘 의 유한 성 - 알고리즘 은 최대 n2 번 while 순환 을 수행 할 때 끝난다. 매번 while 순환 할 때마다 한 남자 가 한 여자 에 게 청혼 을 한다. 모두 n 명의 남자 와 n 명의 여자 가 있 기 때문에 최대 n2 번 만 청혼 을 한다.2. 알고리즘 의 완벽 성 - 모든 남녀 가 짝 짓 기 를 했 습 니 다.그러면 모순 이 생 겨 서 가설 이 성립 되 지 않 고 명제 가 입증 되 었 다.3. 알고리즘 의 안정성 - 불안정 이 존재 하지 않 습 니 다. (반증 법) GS 짝 짓 기 에서 Amy - Yancey, Bertha - Zeus 는 각각 2 쌍 이 고 A - Z 가 불안정 하 다 고 가정 하면 이런 현상 이 나타 날 수 있 습 니 다. a, Z 는 A 에 게 청혼 한 적 이 없습니다. 현상 2 에 따라 Z 는 A 가 아 닌 그의 GS 대상 을 더 좋아 할 것 입 니 다. 그러면 A - Z 는 안정 적 입 니 다.b. Z 는 A 에 게 청혼 을 했 지만 A 에 게 거절당 했다. (즉석에서 거 절 했 을 수도 있 고 나중에 A 가 더 잘 만 나 Z 를 버 렸 을 수도 있다) 그러면 A 가 Z 가 아 닌 GS 상 대 를 더 좋아 한 다 는 것 을 알 수 있 기 때문에 A - Z 도 안정 적 이다.그래서 어떤 상황 에서 도 A - Z 는 안정 적 이 고 가설 이 성립 되 지 않 으 면 명제 가 입증 된다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
#define N 1005
int pref[N][N],order[N][N],next[N];
int future_husband[N],future_wife[N];
queue<int>q;

//  
void engage(int man,int woman){
    int m=future_husband[woman];
    if(m){          //        m
        future_wife[m]=0;//  m
        q.push(m);  //m        
    }
    future_wife[man]=woman;
    future_husband[woman]=man;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                scanf("%d",&pref[i][j]);
            next[i]=1;      //         1     
            future_wife[i]=0;//    
            q.push(i);      //      
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                int x;
                scanf("%d",&x);
                order[i][x]=j;  //    i      ，   x      
            }
            future_husband[i]=0;    //    
        }
        while(!q.empty()){
            int man=q.front();q.pop();
            int woman=pref[man][next[man]++];   //        ，  next    
            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) printf("%d
",future_wife[i]);
        if(t) puts("");
    }
    return 0;
}