[HDOJ 1914] 稳定婚姻系统

题意：

就是稳定婚姻系统的模板题。

对于求出来的每一组配对(a,b)，不能找到(b,c)满足b更喜欢c且c更喜欢b，对于a同样。

分析：

就使一种延迟方法，就使先让他们拍拖然后遇到更好的，就飞掉之前的伴侣。。。

有点邪恶。。。

更详细的讲解请参照：http://hi.baidu.com/leokan/blog/item/4f9b04f719993025730eecef.html

HINT:

1A。

code：

#include #include using namespace std;
int n,ml[27][27],fl[27][27],st[27],bf[27],gf[27],rank[27][27];
char mn[27],fn[27];

int pos(char ch){
    if (ch>=’a’ && ch<='z'){
      for (int i=1;i<=n;i++)
        if (mn[i]==ch) return i;
    }else   
      for (int i=1;i<=n;i++)
        if (fn[i]==ch) return i;
}

void init(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> mn[i];
    for (int i=1;i<=n;i++) cin >> fn[i];
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            ml[i][j]=pos(ch);
        }   
    }   
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            fl[i][j]=pos(ch);
        }   
    }   
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        rank[i][fl[i][j]]=j;
}   

void dfs(int p){
    int i;
    for (i=st[p]+1;i<=n;i++){
        if (bf[ml[p][i]]==0){
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            break;
        }   
        if (rank[ml[p][i]][p]            int tmp=bf[ml[p][i]];
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            dfs(tmp);
            break;
        }   
    }  
    st[p]=i;
}   

void work(){
    memset(st,0,sizeof(st));
    memset(bf,0,sizeof(bf));
    memset(gf,0,sizeof(gf));
    for (int i=1;i<=n;i++)
      if (gf[i]==0) dfs(i);
}   

void print(){
    for (int i=1;i<=n;i++)
      cout << mn[i] << " " << fn[gf[i]] << endl;
}   

int main(){
    int T;
    cin >> T;
    for (int i=1;i<=T;i++){
        init();
        work();
        print();
        if (i!=T) cout << endl;
    }   
}