关于二分图的定义？
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。——摘自百度百科
首先二分图匹配是什么？
个人不喜欢直接上来给这种那种定义，我们拿个例子，伴随这次讲解。随着时代的变迁，你成功的当上了一名大型交友平台主持人，现在在你的节目上，有男生一队，女生一队。而且你知道他们之间谁对谁会有好感，为了人类的繁衍生息，你需要尽可能多的让他们一对一对的匹配。
这里的男一队女一队，就是一个二分图。而进行尽可能多的匹配也就是我们今天解决的问题，二分图最多匹配问题，找出来到底能配对多少对。关于二分图匹配，其实有很多类型，这里我们用匈牙利算法，据说可以解决除了完美匹配外的所有匹配问题。但这里只解决二分图最多匹配问题。
那么什么是匈牙利算法？
所谓的匈牙利算法，放在这里，我们假设每个男生会对大于等于1的小姐姐有好感。我们先给第一个人匹配小姐姐，如果这个小姐姐没有被抢走，我们就撮合他俩，再看下一个人，如果下一个人喜欢的也是上一个小姐姐，我们就移动上一个匹配好的人，让他跟另外有好感的小姐姐连接，然后在把现在要匹配的男生跟他有好感的小姐姐连接。接着第三个，第四个...一直到第N个，都是这样的思路，如果没有跟前面所有的男生冲突，我们就让他连接当前的小姐姐，如果有冲突，就赶走让他前面的男生，让前面的男生让出地方给他。一直赶前面的人直到最一开始的男生发现实在是都换不了了，那这次的哥们就悲剧了。
code
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 inline int read() 7 { 8 int ret=0; 9 char c=getchar(); 10 while (c<'0' || c>'9') c=getchar(); 11 while (c>='0' && c<='9'){ 12 ret=((ret<<3)+(ret<<1))+c-'0'; 13 c=getchar(); 14 } 15 return ret; 16 } 17 const int maxn = 2000; 18 int n, m, e, ans; 19 int vis[maxn], link[maxn], a[maxn][maxn]; //vis是小姐姐的编号，来判断这次匹配中小姐姐有没有被抢走，所以每次要重置0，link[i]就是记录当前小姐姐i和谁连接，有变动就修改，无变动就这样匹配着 20 bool dfs(int x) 21 { 22 for(int i = 1; i <= m; i++)//枚举每个左边点 23 if(a[x][i] && !vis[i])//x对小姐姐i有好感，小姐姐i还没有被抢 24 { 25 vis[i] = 1;//就抢走编号为i的 只要这次有人对i号小姐姐有好感，不管落到谁手里，一定会被抢，所以置为1 26 if(!link[i] || dfs(link[i])) //如果i小姐姐还没有找到，那么就让他们连接，或者是让前面的让出位置来，让他换一个小姐姐 27 { 28 link[i] = x;//当前小姐姐和x连接 29 return 1;//不管赶走多少人，在保证之前可以的情况下，自己只要匹配到，就ans++ 30 } 31 } 32 return 0; 33 } 34 int main() 35 { 36 int u,v; 37 n = read(); m = read(); e = read(); 38 //scanf("%d%d%d",&n,&m,&e); 39 for(int i = 1; i <= e; i++) 40 { 41 u = read(); v = read(); 42 //scanf("%d%d",&u,&v); 43 a[u][v] = 1; 44 } 45 for(int i = 1; i <= n; i++) 46 { 47 memset(vis,0,sizeof(vis)); 48 if(dfs(i)) ans++; 49 } 50 printf("%d ",ans); 51 /*for(int i = 1; i <= n; i++) 52 cout<<link[i]<<" ";*/ 53 for(int i = 1; i <= n; i++) 54 cout<<vis[i]<<" "; 55 return 0; 56 }
