过山车【HDOJ2063】

本文主要是介绍过山车【HDOJ2063】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

匈牙利算法
核心思想：匹配之后，找可修改的匹配，不断回溯。
时间复杂度O（$n^3$）
注意：
邻接矩阵和girl的初始化

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 510;
int line[maxn][maxn],used[maxn],girl[maxn];
int m,n;
int find(int x){for(int i=1;i<=n;i++){if(line[x][i]==1 && used[i]==0){ //该轮妹子还未匹配到 used[i]=1;if(girl[i]==0 || find(girl[i])){ //如果该妹子的男生还可以匹配其他女生，则把该妹子让给当前查找的男生 girl[i]=x;		 return true;}		}}return false;
}
int match(){int sum=0;for(int i=1;i<=m;i++){memset(used,0,sizeof(used));if(find(i)) sum++; }return sum;
}
int main(){int k,u,v;while(cin>>k&&k){cin>>m>>n;memset(line,0,sizeof(line));memset(girl,0,sizeof(girl));while(k--){cin>>u>>v;line[u][v]=1;}cout<<match()<<endl;		}return 0;
} 

这篇关于过山车【HDOJ2063】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---