1 #include<iostream> 2 using namespace std; 3 int main(){ 4     int Smallest_numberFree = 0;//记录单身的号码最低的男性 5     int i = Smallest_numberFree, n, k = -1;//n代表有多少对男女 6      7     cout << "请输出有多少对男女：";  8     cin >> n; 9     int **Man = new int*[n], **Woman = new int*[n];//前者代表每个男性的心中女性的排名，后者代表心中的男性的排名10     int *M_IsFree =new int[n], *W_IsDating=new int[n];//前者-1代表单身，是自由的，后者-1代表还没有约会过,大于-1的值是约会的对象11     int *M_bestWoman = new int[n];//代表每个男人目前未表白的女性中排名最高的人12     int *count = new int[n];//代表每个男性已经表白了多少次13     cout << "请输出男/女性编号从0到" << n - 1 << "的各个心目中女/男性编号0到" << n - 1 << "的排名（空格）：" << endl;14     for (int i = 0; i < n; i++){15         Man[i] = new int[n]; Woman[i] = new int[n];16         cout <<"男"<< i << "号：";17         for (int j = 0; j < n; j++){18             cin >> Man[i][j];19             M_IsFree[j] = -1;20             W_IsDating[j] = -1;21             count[i] = -1;22         }23         M_bestWoman[i] = Man[i][0];24         cout << "女" << i << "号：";25         for (int j = 0; j < n; j++)26             cin >> Woman[i][j];27     }28     while (Smallest_numberFree < n){//若某个男人还是单身29         i = Smallest_numberFree;30         if (W_IsDating[M_bestWoman[i]] == -1){//若男人未表白的女性最赞赏的还未约会31             M_IsFree[i] = M_bestWoman[i];//男人开始与她约会，美好的时光啊32             W_IsDating[M_bestWoman[i]] = i;//女人记录约会的对象33             M_bestWoman[i] = Man[i][++count[i]];//男人记录还未表白的女人中最赞赏的34             Smallest_numberFree++;35         }36         else{37             k = W_IsDating[M_bestWoman[i]];//如果男人看上的女人已经开始约会了，k代表约会的对象的id38             for (int j = 0; j < n; j++){//循环查找女人目前约会的对象和表白的男人之间在女人心中的排名39                 if (Woman[M_bestWoman[i]][j] == k){//如果女人处于约会状态而且目前的对象优于表白的男人40                     M_bestWoman[i] = Man[i][++count[i]];//表白的男人开始找下一个41                     k = -1;//id清零42                     break;43                 }44                 if (Woman[M_bestWoman[i]][j] == i){//如果女人处于约会状态而且对表白者的好感优于目前的约会对象45                     M_IsFree[k] = -1;//把即将被抛弃的男人归为单身46                     M_bestWoman[k] = Man[k][++count[k]];47                     M_bestWoman[i] = Man[i][++count[i]];//表白成功的和被甩的都预定了下一个最赞赏的女性48                     break;49                 }50             }51         }52         if (k != -1){//表示该男人目前单身53             Smallest_numberFree = k;54         }55     }56     cout << "最终生成的稳定匹配是：" << endl;57     cout << "男" << "\t" << "女" << "\t" << endl;58     for (int i = 0; i < n; i++){59         cout << i << "\t" << M_IsFree[i] << "\t" << endl;60     }61     for (int i = 0; i < n; i++){62         delete[] Man[i];63         delete[]Woman[i];64     }65     delete[] W_IsDating;66     delete[] M_bestWoman;67     delete[] M_IsFree;68     delete[] count;69 }