二分图最大匹配

首先，什么是二分图呢？二分图就是能把图中所有点分成两个集合，每个集合中的点两两没有边相连。如下图所示：

二分图最大匹配就是选最多的边，使得这些边中任意两条边没有公共点。怎样求最大匹配数呢？

可以用网络流来解决。

只需要增加源点s和汇点t，然后把每条边的权值设为1，搞个Dinic就可以了。

另外：可以证明：这种算法的时间复杂度是O(sqrt(n)*m)。

附上程序：

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <cmath>#include <vector>#include <queue>using namespace std;#define Maxn 100010#define INF 1000000007int n,m;int s,t;int d[Maxn];int cur[Maxn];struct Edge{	int from,to,cap,flow;	Edge(int x,int y,int v)	{		from = x; to = y; cap = v;		flow = 0;	}};vector<Edge> edges;vector<int> f[Maxn];void AddEdge(int x,int y,int v){	edges.push_back(Edge(x,y,v));	edges.push_back(Edge(y,x,0));	int m = edges.size();	f[y].push_back(m-1);	f[x].push_back(m-2);}bool vis[Maxn];bool bfs(int s,int t){	queue<int> q;	memset(vis,0,sizeof(vis));	vis[s] = true;	q.push(s);	d[s] = 0;		int u;	while(!q.empty())	{		u = q.front(); q.pop();		int len = f[u].size();		for(int i=0;i<len;i++)		{			Edge e = edges[ f[u][i] ];			if((!vis[e.to]) && e.flow<e.cap)			{				q.push(e.to);				d[e.to] = d[u] + 1;				vis[e.to] = true;			}		}	}	return vis[t];}int dfs(int u,int a){	if(u==t || a==0) return a;	int len = f[u].size();	int flow,r;	flow = 0;	for(int& i=cur[u];i<len;i++)	{		Edge &e = edges[f[u][i]];		Edge &_e = edges[f[u][i]^1];		if(d[e.to] == d[u]+1 && (r = dfs(e.to,min(a,e.cap-e.flow)))>0)		{			e.flow+=r;			_e.flow-=r;			flow+=r;			a-=r;			if(a==0) break;		}	}	return flow;}int Dinic(int s,int t){	int flow = 0;	while(bfs(s,t))	{		memset(cur,0,sizeof(cur));		flow += dfs(s,INF);	}	return flow;}int main(){	int x,y,q;	scanf("%d%d%d",&n,&m,&q);	s = 0; t = n + m + 1;	//建模 	for(int i=1;i<=n;i++) AddEdge(s,i,1);	for(int i=1;i<=m;i++) AddEdge(i+n,t,1);	for(int i=1;i<=q;i++)	{		scanf("%d%d",&x,&y);		AddEdge(x,y+n,INF);	}	//Dinic算法 	PRintf("%d/n",Dinic(s,t));	return 0;}