题意：n个男生和女生，先是n行n个数，表示每一个女生对男生的好感值排序，然后是n行n列式每一个男生的好感值排序，输出N行，即每个女生在最好情况下的男生的编号
分析：如果是求女生的最好情况下，就要从女生开始选，这样女生都是从最好的到不好的来选，而男生却相反--只能娶那些自己有可能最没好感的女生，因为男生是被动的，他最喜欢的女生不见的会向他求婚。
刘汝佳书上命名错了，so也跟着把男生当成女生了，懒得改命名了，
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int Max = 1010; 8 int pref[Max][Max], order[Max][Max], Next[Max]; 9 int future_hasband[Max], future_wife[Max];10 queue q; //单身女生队列11 void engage(int man, int woman)12 {13 int m = future_hasband[woman];14 if(m)15 {16 future_wife[m] = 0;17 q.push(m);18 }19 future_hasband[woman] = man;20 future_wife[man] = woman;21 return;22 }23 int main()24 {25 int T;26 scanf("%d", &T);27 while(T--)28 {29 int n;30 scanf("%d", &n);31 while(!q.empty())32 q.pop();33 for(int i = 1; i <= n; i++)34 {35 for(int j = 1; j <= n; j++)36 scanf("%d", &pref[i][j]);37 future_wife[i] = 0; // 女生i没有匹配38 Next[i] = 1; // 都是从第一个开始查找39 q.push(i); // 加入单身队列40 }41 for(int i = 1; i <= n; i++)42 {43 for(int j = 1; j <= n; j++)44 {45 int x;46 scanf("%d", &x);47 order[i][x] = j; // 表示男生i 对 女生 x 的好感等级48 }49 future_hasband[i] = 0;50 }51 while(!q.empty())52 {53 int man = q.front();54 q.pop();55 int woman = pref[man][Next[man]++];56 if(future_hasband[woman] == 0) // 表示这个男生并没有 匹配57 engage(man, woman);58 else if(order[woman][man] < order[woman][future_hasband[woman]]) // 虽然已经匹配了，但是同已经匹配的好感层度来看，更喜欢这个59 engage(man, woman);60 else 61 q.push(man); // 否则继续单身，等待下次解救62 }63 for(int i = 1; i <= n; i++)64 printf("%d\n", future_wife[i]);65 if(T)66 printf("\n");67 }68 69 return 0;70 }