不得不说，如果以现实角度代入此算法的理解，就合理了很多，虽然有悖道德准则
重点在于以下几点
- 每次给女生分配男生前，都把男生全部初始化为可预定状态（即使他已经被别人成功匹配了）
- 在所有女生中意的男生中遍历，如果发现该男生可预订就先预定，然后看他是否已经有主了，如果有主了，就
dfs(match[i])，（跟当前那个匹配这个男生的女生商量能不能换，此时 dfs 进去，该男生预定状态是还在的，所以不会出岔子），当然这一步正经来说叫寻找增广路
然后是代码：
点击查看代码
int n, m;
int match[N], reserve[N];
int G[510][510];
bool dfs(int u){
// u For Girl, i For Boy;
for(int i = 1; i <= m; i++){
if(!reserve[i] && G[u][i]){
reserve[i] = 1;
if(!match[i] || dfs(match[i])){
match[i] = u;
return true;
}
}
}
return false;
}
由于匈牙利算法是O(nm)的，所以直接用邻接矩阵存图就好了
标签：二分,图论,匹配,int,dfs,算法,男生,女生 From： https://www.cnblogs.com/9102qyy/p/18211131