本文主要是介绍HDU 2063 过山车（匈牙利算法模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2063
分析与总结：
这题是裸的二分匹配，用来验证模板的
代码：
1. DFS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 505;
int Nx,Ny;
int G[MAXN][MAXN];
int Mx[MAXN], My[MAXN];
bool mark[MAXN];bool FindPath(int u){for(int v=0; v<Ny; ++v){if(G[u][v] && !mark[v]){mark[v] = true;if(My[v]==-1 || FindPath(My[v])){My[v] = u;Mx[u] = v;return true;}}}return false;
}
int MaxMatch(){int ret=0;memset(Mx, -1, sizeof(Mx));memset(My, -1, sizeof(My));for(int u=0; u<Nx; ++u){if(Mx[u] == -1) {memset(mark, 0, sizeof(mark));if(FindPath(u)) ++ret;}}return ret;
}int main(){int k,a,b;while(~scanf("%d%d%d",&k,&Nx,&Ny) && k){memset(G,0,sizeof(G));for(int i=0; i<k; ++i) {scanf("%d%d",&a,&b);G[a-1][b-1]=1;}printf("%d\n",MaxMatch());}return 0;
}
2. BFS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 505;
int Nx,Ny;
int G[MAXN][MAXN];
int Mx[MAXN], My[MAXN], prev[MAXN], Q[MAXN];
int mark[MAXN];int MaxMatch(){int res = 0;int front, rear;memset(Mx, -1, sizeof(Mx));memset(My, -1, sizeof(My));memset(mark, -1, sizeof(mark));for (int i = 0; i < Nx; i++){if (Mx[i] == -1){front = rear = 0;Q[rear++] = i;prev[i] = -1;bool flag = 0;while (front < rear && !flag){int u = Q[front];for (int v = 0; v < Ny && !flag; v++){if (G[u][v] && mark[v] != i){mark[v] = i;Q[rear++] = My[v];if (My[v] >= 0)prev[My[v]] = u;else{flag = 1;int d = u, e = v;while (d != -1){int t = Mx[d];Mx[d] = e;My[e] = d;d = prev[d];e = t;}}}}front++;}if (Mx[i] != -1)res++;}}return res;
}
int main(){int k,a,b;while(~scanf("%d%d%d",&k,&Nx,&Ny) && k){memset(G,0,sizeof(G));for(int i=0; i<k; ++i) {scanf("%d%d",&a,&b);G[a-1][b-1]=1;}printf("%d\n",MaxMatch());}return 0;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于HDU 2063 过山车（匈牙利算法模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
