二分图 匹配问题举例 模型的建立?

来源:百度知道 编辑:UC知道 时间:2024/07/07 05:53:43

(赏点分吧!?)
poj上有很多题,1274就是典型的二分图匹配
http://acm.pku.edu.cn/JudgeOnline/problem?id=1274
代码:
#include <iostream>
using namespace std;

int map[205][205], m, n, cy[205], f[205];

int path(int t){
int i, j, k;
for(i=1;i<=m;i++){
if(f[i]==0 && map[t][i]){
f[i] = 1;
if(cy[i]==-1 || path(cy[i])){ //这里的“||”是需要慢慢理解的
cy[i] = t;
return 1;
}
}
}
return 0;
}

int maxMatch(){
int i, j, k, co=0;
memset(cy, 0xff, sizeof(cy));
for(i=1;i<=n;i++){
memset(f, 0, sizeof(f));
if(path(i)){