首页 > 代码库 > poj 3487 稳定婚姻
poj 3487 稳定婚姻
1 /** 2 稳定婚姻:男生不停的求婚,女生不停地拒绝 3 **/ 4 5 #include <iostream> 6 #include <queue> 7 #include <cstdio> 8 #include <cstring> 9 using namespace std; 10 #define maxn 40 11 int pref[maxn][maxn],order[maxn][maxn],next[maxn]; 12 int future_wife[maxn],future_huaband[maxn]; 13 int man[maxn]; 14 queue<int > q; 15 char str[50]; 16 void engage(int man,int woman){ 17 int m = future_huaband[woman]; 18 if(m){ 19 future_wife[m] =0; 20 q.push(m); 21 } 22 future_huaband[woman] = man; 23 future_wife[man] = woman; 24 } 25 int main() 26 { 27 int t; 28 scanf("%d",&t); 29 while(t--){ 30 memset(man,0,sizeof(man)); 31 int n; 32 scanf("%d",&n); 33 char c; 34 for(int i=0;i<n;i++){//男 35 cin>>c; 36 man[c-‘a‘+1] =1; 37 } 38 for(int i=0;i<n;i++)//女 39 cin>>c; 40 for(int i=1;i<=n;i++){//男喜欢 41 cin>>str; 42 //cout<<str<<endl; 43 int temp = str[0]-‘a‘+1;//哪个男生 44 //cout<<temp<<endl; 45 for(int j=2;str[j];j++){ 46 pref[temp][j-1] = str[j]-‘A‘+1; 47 //cout<<pref[temp][j]<<endl; 48 } 49 next[temp] = 1; 50 future_wife[temp] =0; 51 q.push(temp); 52 } 53 for(int i=1;i<=n;i++){ 54 cin>>str; 55 //cout<<str<<endl; 56 int temp = str[0]-‘A‘+1; 57 for(int j=2;str[j];j++){ 58 order[temp][str[j]-‘a‘+1] = j-1; 59 } 60 future_huaband[temp] =0; 61 } 62 while(!q.empty()){ 63 int man = q.front(); 64 q.pop(); 65 int woman = pref[man][next[man]++]; 66 if(!future_huaband[woman]){ 67 engage(man,woman); 68 }else if(order[woman][man]<order[woman][future_huaband[woman]]){ 69 engage(man,woman); 70 }else 71 q.push(man); 72 } 73 while(!q.empty()) q.pop(); 74 for(int i=1;i<maxn;i++)if(man[i]){ 75 printf("%c %c\n",(char)(i-1+‘a‘),(char)(future_wife[i]-1+‘A‘)); 76 } 77 if(t) 78 printf("\n"); 79 } 80 return 0; 81 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。