HDU 2063 过山车 匈牙利算法
本菜鸡终于自己走了一遍,感觉很妙,但是总觉得自己想的话想不到这个递归结构。
还是太菜了。要多练练递归(感觉还是会想不到
#include<iostream> #include<cstring> using namespace std; const int N = 510; //腾 int n, m;//男生 女生 int g[N][N];//graph 描述图关系 int vis[N], boy[N]; bool dfs(int x) { for(int i = 1; i <= n; i++) {//遍历每个男生 if(!vis[i] && g[x][i]) {//如果存在关系且没有被访问过 vis[i] = 1;//访问记录 if(!boy[i] || dfs(boy[i])) {//如果男生名花无主或者可以挪动 boy[i] = x; return 1; } } } return 0; } int main() { int k; while(cin >> k && k) { cin >> m >> n; memset(g, 0, sizeof(g)); memset(boy, 0, sizeof(boy)); for(int i = 0; i < k; i++) { int a, b; cin >> a >> b; g[a][b] = 1; } int sum = 0; for(int i = 1; i <= m; i++) {//遍历每一个女生 memset(vis, 0, sizeof(vis));//每一个女生都清空访问记录 if(dfs(i)) sum++; } cout << sum << endl; } return 0; }
补充WuTao大佬的话,以后来看:
二分图最大匹配。
可以用最大流解决。也可以用匈牙利算法。匈牙利算法是最大流方法的一种优化。若采用邻接矩阵存图,时间复杂度 O(V2),空间复杂度 O(V2)。若采用邻接表,时间复杂度 O(VE),空间复杂度 O(V+E)。