网络流（二分图）
匈牙利算法
主要的思想是利用点的让位关系，如果可以让位那就进行一位位的让出。实际上如果用网络流来进行分析，设S为源点，从S到左图每一个点连一条流量为1的边，从右图开始每一个点连一条流量为1的边到T点，中间为题目给出的路径。实际上分析匈牙利算法是在利用EK算法找残留网络的增广路径，所以时间复杂度为O(nm)。
bool Hungary(int p)
{
//used每一次都要初始化，代表没有被使用。
for(int j=1;j<=n;j++) //遍历每一个点
if(!used[j]&&f[p][j]==1) //有路径同时没有被使用
{
used[j]=1;
if(vis[j]==0||Hungary(vis[j])){
vis[j]=p;
return true;
}
}
return false;
}网络流解二分
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e4+10,M=2e5+10;
int n,m,S,T,sum;
int head[N],idx,q[N],d[N],cur[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i; //当前弧优化
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1; //如果直接没有流量，就直接把这个点删除
edge[i].f-=t; edge[i^1].f+=t; flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs()) while(flow=find(S,inf)) res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d%d",&n,&m,&sum); S=0,T=m+n+1;
for(int i=1;i<=n;i++) add(S,i,1);
for(int i=1;i<=m;i++) add(i+n,T,1);
int a,b;
while(sum--)
{
cin>>a>>b;
add(a,b+n,1);
}
printf("%d\n",dinic());
return 0;
}