匈牙利算法
二分图：把一个图的顶点划分为两个不相交集 U 和 V ，使得每一条边都分别连接U 、 V 中的顶点。如果存在这样的划分，则此图为一个二分图。
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图 3、图 4 中红色的边就是图 2 的匹配。
匹配点、匹配边、未匹配点、非匹配边：例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图4 是一个最大匹配，它包含 4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int MaxN=; int N,M;
int Ans;
int link[MaxN];
bool cover[MaxN];
bool Map[MaxN][MaxN]; void init()
{
int i,x,y;
scanf("%d%d",&N,&M);
memset(Map,false,sizeof(Map));
for(i=;i<=M;++i)
{
scanf("%d%d",&x,&y);
Map[x][y]=true;
}
}
bool Find(int i)
{
int j;
for(j=;j<=N;++j)
if(Map[i][j] && !cover[j])
{
cover[j]=true;
if(!link[j] || Find(link[j]))
{
link[j]=i;
return true;
}
}
return false;
}
void solve()
{
int i;
memset(link,,sizeof(link));
for(i=;i<=N;++i)
{
memset(cover,false,sizeof(cover));
Find(i);
}
}
void print()
{
int i;
Ans=;
for(i=;i<=N;++i)
if(link[i])
Ans++;
printf("%d\n",Ans);
for(i=;i<=N;++i)
if(link[i])
printf("%d %d\n",link[i],i);
}
int main()
{
init();
solve();
print();
return ;
}
例一：二分图
给定一个图（可能为非联通图），将其二分，得到两个数组，输出其中某个数组的个数和顶点？
输入用例（二分图检测）：
算法代码：
#include <stdlib.h>
#include <stdio.h>
#include <string.h> #define MAX 1001 int path[MAX][MAX] = {};
int c[MAX] = {};
int group[MAX] = {};
int count = ;
int N, E;
int value[] = {, , };
int partition(int start) //给每个点分组，存到group[]
{
for(int i = ; i < c[start]; i++)
{
int city = path[start][i];
if(group[city] != )
{
if(group[city] == group[start])return ; //相邻两个点分组一样，则返回0，不是二分图
}
else
{
group[city] = value[group[start]];
if (group[city] == )count++;
if(!partition(city))return ;
}
} return ;
} int getNoGroup(int * pt)
{
for (int i = ; i <= N; i++)
{
if (!group[i])
{
*pt = i;
return ;
}
} return ;
} int main(void)
{
freopen("input3.txt", "r", stdin);
//freopen("output.txt", "w", stdout); for(int test_case = ; test_case <= ; test_case++)
{
scanf("%d %d\n", &N, &E);
for(int i = ; i < E; i++)
{
int pt1, pt2;
scanf("%d %d", &pt1, &pt2);
path[pt1][c[pt1]++] = pt2;
path[pt2][c[pt2]++] = pt1;
} int start = ;
bool errorFlag = false; //判断是否是二分图
while(getNoGroup(&start)) //当非连通图的时候，也能遍历到
{
group[start] = ;
if(!partition(start))
{
errorFlag = true;
break;
}
} if(errorFlag)printf("#%d -1\n", test_case);
else
{
printf("#%d %d", test_case, count);
for(int i = ; i <= N; i++)if(group[i] == )printf(" %d", i);
printf("\n");
} memset(group, , MAX*);
memset(path, , MAX*MAX*);
} return ;
}
例二：圣诞礼物
给定人数和礼物数量，接下来给出每个人喜欢的礼物的编号，求最大匹配？
输入用例（二分图最大匹配）：
算法代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std; #define MAX 401 int map[MAX][MAX] = { }; //第i个人的每个礼物的编号
int c[MAX] = { }; //第i个人一共可能连多少个礼物
int check[MAX] = { }; //表示当前第i个人已经遍历过的礼物编号
int matching[MAX] = { }; //礼物和人匹配的状态 bool dfs(int u)
{
for (int i = ; i < c[u]; i++)
{
int v = map[u][i];
if (!check[v])
{
check[v] = true;
if(matching[v] == || dfs(matching[v]))
{
matching[v] = u;
matching[u] = v;
return true;
}
}
}
return false;
} int main(int argc, char** argv)
{
freopen("input.txt", "r", stdin);
int case_max;
scanf("%d\n", &case_max);
for(int case_num = ; case_num < case_max; case_num++)
{
int personCnt, giftCnt;
scanf("%d %d\n", &personCnt, &giftCnt);
for(int i = ; i <= personCnt; i++)
{
int favoriteCnt;
scanf("%d ", &favoriteCnt);
for(int j = ; j <= favoriteCnt; j++)
{
int favorite;
scanf("%d", &favorite);
//map[i].push_back(personCnt+favorite);
map[i][c[i]++] = personCnt + favorite;
map[personCnt + favorite][c[personCnt + favorite]++] = i;
}
} int result = ;
for(int i = ; i <= personCnt; i++)
{
if (matching[i] == )
{
memset(check, , sizeof(check));
if(dfs(i))result++;
}
} printf("%d\n", result); memset(map, , sizeof(int)*MAX*MAX);
}
}