bool bSingle=false; while(!bSingle){ bSingle=true; for(i=0;i<N;i++){ if(match[i]!=-1) // boy i already have a girlfriend continue; bSingle=false; j=manIndex[i]++; // the jth girl that boy i like most w=man[i][j]; m=choose[w]; // current girl w's boyfriend if(m==-1 || wm[w][i]<wm[w][m]){ // if girl w prefer boy i match[i]=w; choose[w]=i; if(m!=-1) match[m]=-1; } }
时间: 2024-02-14 22:35:10 浏览: 15
这段代码实现了稳定婚姻匹配算法的过程,其中:
- match[i]表示男性i匹配的女性编号,如果match[i]=-1,则表示男性i还没有匹配到女性;
- choose[w]表示女性w匹配的男性编号,如果choose[w]=-1,则表示女性w目前没有男友;
- man[i]表示男性i对女性的偏好列表,man[i][j]表示男性i对第j个女性的偏好;
- wm[w][i]表示女性w对男性i的偏好程度,其中偏好程度越高,值越小。
这个算法的核心思想是,从男性的角度出发,依次让每个男性向他最喜欢的女性求婚。如果女性当前没有匹配对象,则接受这个男性的求婚;如果女性已经有了男友,但是这个男性比当前男友更优秀,则女性会和这个男性分手,和新的男友在一起。在这个过程中,如果男性i被女性w拒绝了,那么他会继续向他的下一个偏爱的女性求婚,直到找到一个女性接受他的求婚。
这个算法最终的结果是稳定的匹配,即不存在两个男性和女性之间有更好的匹配方案。这个算法的时间复杂度是O(n^2),其中n是男性和女性的数量。
相关问题
bool i=true; if(!i) return i;
根据这段代码,变量i被定义为true,然后在if语句中使用逻辑非运算符!将其取反,即变为false。因此,if语句的条件为false,不满足条件,不会执行其中的代码。最后,程序返回变量i的值,即true。因此,这段代码实际上等价于:
```c++
bool i = true;
return i;
```
它的作用是将变量i的值返回。
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 10; int n, m; int a[N]; int main() { cout << "请输入结点数:" << endl; while (cin >> n >> m) //输入图1、2的结点数 { if (m != n) { cout << "两图不同构!!!" << endl; continue; } //根据结点数n、m,动态生成两个二维数组来存图(使用邻接矩阵的方式) vector<int> w1(n + 1, 0); vector<vector<int> > g1(n + 1, w1); vector<int> w2(m + 1, 0); vector<vector<int> > g2(m + 1, w2); for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组 for (int i = 1; i <= n; i++) //输入图1的邻接矩阵 for (int j = 1; j <= n; j++) cin >> g1[i][j]; for (int i = 1; i <= m; i++) //输入图2的邻接矩阵 for (int j = 1; j <= m; j++) cin >> g2[i][j]; //全排列 do { bool f = 0; int temp[N][N]; memset(temp, 0, sizeof temp); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { temp[i][j] = g1[a[i]][a[j]]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (temp[i][j] != g2[i][j]) { f = 1; break; } } if (f == 1) break; } if (f == 0) cout << "两图同构^-^" << endl; } while (next_permutation(a + 1, a + 1 + n)); cout << "两图不同构!!!" << endl; } return 0; }简化的完整代码
这是一个判断两个图是否同构的程序,输入两个图的邻接矩阵,通过枚举两个图的节点的排列顺序,判断它们是否同构。如果是同构的,则输出"两图同构^-^",否则输出"两图不同构!!!"。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
int n, m;
int a[N];
int main() {
cout << "请输入结点数:" << endl;
while (cin >> n >> m) { //输入图1、2的结点数
if (m != n) {
cout << "两图不同构!!!" << endl;
continue;
}
//根据结点数n、m,动态生成两个二维数组来存图(使用邻接矩阵的方式)
vector<int> w1(n + 1, 0);
vector<vector<int> > g1(n + 1, w1);
vector<int> w2(m + 1, 0);
vector<vector<int> > g2(m + 1, w2);
for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组
for (int i = 1; i <= n; i++) //输入图1的邻接矩阵
for (int j = 1; j <= n; j++)
cin >> g1[i][j];
for (int i = 1; i <= m; i++) //输入图2的邻接矩阵
for (int j = 1; j <= m; j++)
cin >> g2[i][j];
//全排列
do {
bool f = 0;
int temp[N][N];
memset(temp, 0, sizeof temp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
temp[i][j] = g1[a[i]][a[j]];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (temp[i][j] != g2[i][j]) {
f = 1;
break;
}
}
if (f == 1) break;
}
if (f == 0) cout << "两图同构^-^" << endl;
} while (next_permutation(a + 1, a + 1 + n));
cout << "两图不同构!!!" << endl;
}
return 0;
}
```