HDU 2063过山车 解题报告（我的第一道二分匹配）
下面是复制别人的解析后根据我不懂的地方自己补充修改的：
二部图（也叫二分图）概念：
1．何为二部图
如果V(G)可以分到两个集合X，Y中，且X和Y内部没有G的边．那么图G就是一个二部图（等价于图G是可二顶点着色的）下图便是一个二部图．
2．二部图的性质
一个图是二部图当且仅当图G中没有奇环．比如说一个三角形就不可能分成两个部分，并且每个部分内部没有边，但一个正方形就可以．
3．如何得到二部图的每个部分
任意选一个顶点，所有到该点距离为偶数的点构成的集合便是G中的一部分，距离为奇数的点为另一部分
4．何为匹配
图G的一个匹配是一组没有公共端点的边构成的集合，如（图一）两条黑色的边（1,4、2,5）构成一个大小为２的匹配，三条红色的边（1,4、2,5、3,6）构成一个大小为３的匹配．图中的最大匹配数就是３。
该题就是求解一个二分图的最大匹配，判定一个匹配是不是最大匹配就是通过寻找增广路径。如何寻找呢？
假设该题中女生为X部，男生为Y部，定义几个变量，G[u][i]代表u，i两点之间的连接情况，marry[i] =u表示Y部中的第i个男生与女生u配对，visit[i] 表示Y部中第i个男生有没有女生找过，两个数组初始化为0。
在每次寻找增广路径时，我们都将visit[i]重置，因为每次寻找增广路径就是让他们每个男生都有重新选择的机会，然后判定这种新的匹配方式能否产生更多的匹配。
step1：从一个女生开始，扫描所有在另外一个部分（Y部）与之相连的点，没有边或者已经给过机会的男生（他们或许已经找到新另一半，或者他不愿与前女伴分手）的不予考虑。
for (int i = 1; i <= N; ++i) {
if (!G[u][i] || visit[i])
continue;
......
}
step2：两两之间有边，并且第i个男生在这一轮新的配对中暂时没有被女生找到的话（就是step1的if判定失败），那么这个男生就算被女生找过了。
visit[i] = 1;
step3：现在我们这样来办，如果第i个男生之前没有女生配对的话，那么马上将他们联系起来，因为这必将是新的一对，并且返回1，表示寻找到了增广路径。还有一种情况，那就
该男生之前有女生配对，那么我们就策划让其以前配对的女生另外找一个男生，这不难实现，再次调用这个函数即可。
if (!marry[i] || path(marry[i])) {
marry[i] = u;
return 1;
}
step4：如果所有的男生由于各种原因都不愿与该女生配对的话，返回0，表示寻找增广路径失败。
我们调从外部调用这个函数N次（N代表女生的个数），表示每次抱着给这个女生找有好男友的决心，虽然过程中可能会拆散其他对，但我能保证只有当新配对的人数多余上次匹配结果我才这样去做。
注意：1.假设是第k次从外部调用该函数的话，执行该函数的过程中一定不会牵涉到第k+1到N号女生的匹配情况，因为我们每次顶多是拆散以前的配对过的女生去完成新匹配。
2.为什么能保证配对的对数增加呢？如果函数执行成功，我们为第k号女生完成了匹配，并且为所有为之被拆散的女生找到了新的对象，所以匹配数会增加1。
一个匹配M是图G的最大匹配当且仅当图G中不存在M-增广路径. M-增广路径是一条边交替出现在匹配M和不出现在匹配M中的路径，且两个端点没有被M中的边覆盖。若是一个图有M-增广路径，就得到了一个更大的匹配。所谓交替出现在M和不出现在M中的路径就是撮合一对，拆散一对的过程。
代码如下：
[cpp]
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int map[505][505],vb[505],marryb_g[505];
int k,n,m;
int getpath(int u)
{
int i;
for(i=1;i<=m;i++)
{
if(!map[u][i] || vb[i])
continue;
vb[i]=1;
if(!marryb_g[i] || getpath(marryb_g[i]))
{
marryb_g[i]=u;
return 1;
}
}
return 0;
}
int main()
{
int i,a,b;
while(scanf("%d",&k)!=EOF && k)
{
memset(map,0,sizeof(map));
memset(marryb_g,0,sizeof(marryb_g));
scanf("%d%d",&n,&m);
for(i=0;i<k;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=1;
}
int ans=0;
for(i=1;i<=n;i++)
{
memset(vb,0,sizeof(vb));
if(getpath(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
补充：软件开发 , C++ ,
