匈牙利算法（别名“找对象游戏”），就是给你一个二分图，求最大匹配。
最大匹配就是做多能连多少条边。
我们把这个抽象的概念转化成现实问题——找对象。
男女两组，男生A组，女生B组，每一个男生都有自己喜欢的女生（可能不止一个），作为上帝的你，尽可能的让更多的人成为男女朋友。
怎么做呢？
枚举每一个男生，要求尽可能找到女朋友，但要保证前面的人可以更换女朋友，但是原来有女朋友的现在必须都有女朋友，这样如果能行，那么答案+1。
枚举所有男生后就得到了答案。
这就是匈牙利算法的主要思想——增广路。
奉上夏令营zyb老师的课件：
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 const int maxn=1000005; 8 int n,m,E,p[2005],cnt,ans; 9 bool vis[2005]; 10 int girl[2005]; 11 struct node{ 12 int v,next; 13 }e[2*maxn]; 14 void insert(int u,int v){ 15 cnt++; 16 e[cnt].v=v; 17 e[cnt].next=p[u]; 18 p[u]=cnt; 19 } 20 bool work(int u){ 21 for(int i=p[u];i!=-1;i=e[i].next){ 22 if(!vis[e[i].v]){ 23 vis[e[i].v]=1; 24 if(!girl[e[i].v]||work(girl[e[i].v])){ 25 girl[e[i].v]=u; 26 return true; 27 } 28 } 29 } 30 return false; 31 } 32 int main() 33 { 34 memset(p,-1,sizeof(p)); 35 cin>>n>>m>>E; 36 for(int i=1;i<=E;i++){ 37 int u,v; 38 scanf("%d%d",&u,&v); 39 if(u<=n&&v<=m){ 40 insert(u,v+1000); 41 insert(v+1000,u); 42 } 43 } 44 for(int i=1;i<=n;i++){ 45 memset(vis,0,sizeof(vis)); 46 if(work(i)) ans++; 47 } 48 cout<<ans; 49 return 0; 50 }
原文：https://www.cnblogs.com/yinyuqin/p/12181706.html