（老弱病残康复训练）51nod 2006 飞行员配对 （二分图匹配）

点击打开题目链接

在说二分图匹配之前，必须先点个前置技能：二分图是什么。匹配是什么。

二分图：二分图研究的是一类无向图问题。G=（V，E）是一个无向图，如果定点V可以分割为两个互不相交的自己（X，Y），并且途中的每条边（i，j）所关联的两个定点i，j分别属于这个两个不同的定点集，那么就称这个图为二分图。记为G = （X，Y；E）；

匹配：给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

这里我打算放几个图来解释

这是一个匹配。

这是一个完美匹配。

对于二分图来说，一般处理的的都是二分图最大匹配。处理二分图最大匹配问题一般会用到匈牙利算法。

一下：X，Y表示二分图的两个集合。

匈牙利算法：通俗一点来说就是对于集合X，按照给定的图关系依次给集合X中的元素添加匹配。若某个Xi没有Yi可以匹配。那么尝试把能与Xi匹配的一个Yi改变归属。（这是一个递归的过程）。=-= 博主讲的比较脑残。就不打算多解释，放一个博主学习的博客，写的很好大家可以去看看。

http://blog.csdn.net/dark_scope/article/details/8880547

直接上博主的脑残代码（有点不一样的是，博主用的是链式前向星的存图）

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int MAXN = 105;
const int MAXE = 1e5 + 10;struct edge{int v;int nt;
};
int n,m;
int ans ,tot;
int head[MAXN];
int match[MAXN];
bool flag[MAXN];
edge map[MAXE];void add_edge (int x,int y){tot ++;map[tot].v = y;map[tot].nt = head[x];head[x] = tot;
}void init(){memset(head,0,sizeof(head));memset(match,0,sizeof(match));ans = tot = 0;
}bool dfs (int x){for(int e = head[x];e;e = map[e].nt){int v = map[e].v ;if(!flag[v]){flag[v] = true;if(match[v] == 0 || dfs(match[v])){match[v] = x;return true;}}}return false ;
}void hungary(){for(int i = 1 ;i <= m ; i++){memset(flag,false,sizeof(flag));if(dfs(i))ans ++;}
}
int main(){init();scanf("%d%d",&m,&n);int x,y;while(scanf("%d%d",&x,&y),x != -1 && y !=-1){add_edge(x,y);}hungary();printf("%d\n",ans);return 0;
}