无权二分图的最大匹配(匈牙利算法)

二分图的最大匹配——匈牙利算法(是对最大流方法求最大匹配的改进，提高了效率)，先来了解一下二分图，顾名思义，二分图是可以将所有点分成两个部分的图，怎么判断呢，可以这么来，我们暂且将红色和蓝色看成两种相反的颜色，将图中的某一个顶点涂为红色，然后将和它相连的顶点涂成黑色的颜色，即与它本身相反的颜色，继续如此，如果按照这种方法可以将全部顶点都着色的话，那么该图就是一个二分图。 二分图的最大匹配，其实就是不断寻找增广路，增广路本质是一条路径上的起点和终点都是未匹配的点。

举个栗子，分别有3个男生和3个女生，将他们分组，只能认识的一男一女在一组，这里假设男1和女1认识，男1还和女3认识，男2和女1认识，男2还和女2认识，男3和女2认识。首先很容易先分成 男1和女1一组，男2和女2一组，可男3和女3不认识，不能组成一组。然而发现女3还和男1认识，因此打算和男1一组，可男1和女3一组之后，女1无人一组了，又发现女1和男2认识，所以，女1打算和男2一组，此时女2又没人一组了，而女2恰好认识男3，而男3正好也无人一组，因此女2和男3组成一组，从而找到了一条增广路，增加了匹配数，我们发现起点和终点都是刚开始未匹配同伴的人。

//二分图的最大匹配-寻找增广路 #include <iostream> #include <cstdio> using namespace std; int match[105], e[105][105], book[105]; int n, m; int dfs(int c){ int i; for(i = 1; i <= n; ++i){ if(book[i] == 0 && e[c][i] == 1){ book[i] = 1; if(match[i] == 0 || dfs(match[i])){ match[i] = c; match[c] = i; return 1; } } } return 0; } int main(){ int sum, i, j, a, b; cin >> n >> m; for(i = 1; i <= m; ++i){ cin >> a >> b; e[a][b] = e[b][a] = 1; } sum = 0; for(i = 1; i <= n; ++i) match[i] = 0; for(i = 1; i <= n; ++i){ for(j = 1; j <= n; ++j) book[j] = 0; if(match[i] != 0) continue; //这里是n个点中最多找到n/2个匹配，也就是说关系是n个点之间的 //这句话很关键，如果没有这句，4 2, 1 4, 2 4这个测点便是错误 if(dfs(i)) ++sum; } printf("%d\n", sum); return 0; }