方法
二分图转换成网络流模型；创建虚拟源点和汇点，将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。
code:洛谷P3386
dinic:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=510,M=1e5+10+(N<<2);
struct edge{LL v,c,ne;}e[M];
int h[N<<1],id=1;
int cur[N<<1],s,t,dep[N<<1];
int n,m,num;
void add(int u,int v,int c){e[++id]={v,c,h[u]};h[u]=id;
}bool bfs(){memset(dep,0,sizeof(dep));queue<int> q;q.push(s);dep[s]=1;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(dep[v]==0&&e[i].c){dep[v]=dep[u]+1;q.push(v);if(v==t)return true;}}}return false;
}LL dfs(int u,LL mf){if(u==t)return mf;LL sum=0;for(int i=cur[u];i;i=e[i].ne){cur[u]=i;int v=e[i].v;if(dep[v]==dep[u]+1&&e[i].c){LL f=dfs(v,min(mf,e[i].c));sum+=f;mf-=f;e[i].c-=f;e[i^1].c+=f;if(mf==0)break;}}if(sum==0)dep[u]=0;return sum;
}int dinic(){int flow=0;while(bfs()){memcpy(cur,h,sizeof(h));flow+=dfs(s,1e9);}return flow;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>num;for(int i=1;i<=num;i++){int u,v;cin>>u>>v;add(u,v+n,1);add(v+n,u,0);}s=0;t=n+m+1;for(int i=1;i<=n;i++){add(s,i,1);add(i,s,0);}for(int i=1;i<=m;i++){add(i+n,t,1);add(t,i+n,0);}cout<<dinic()<<endl;return 0;
}
EK:
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1e5+10+(N<<1);
typedef long long LL;
struct edge{LL v,c,ne;}e[M];
int h[N],id=1;
int mf[N],pre[N];
int n,m,num,s,t;
void add(int u,int v,int c){e[++id]={v,c,h[u]};h[u]=id;
}bool bfs(){memset(mf,0,sizeof(mf));queue<int> q;q.push(s);mf[s]=1e9;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(mf[v]==0&&e[i].c){mf[v]=min(1ll*mf[u],e[i].c);q.push(v);pre[v]=i;if(v==t)return true;}}}return false;
}LL EK(){LL flow=0;while(bfs()){flow+=mf[t];int v=t;while(v^s){int i=pre[v];e[i].c-=mf[t];e[i^1].c+=mf[t];v=e[i^1].v;}}return flow;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>num;for(int i=1;i<=num;i++){int u,v;cin>>u>>v;add(u,v+n,1);add(v+n,u,0);}s=0;t=n+m+1;for(int i=1;i<=n;i++){add(s,i,1);add(i,s,0);}for(int i=1;i<=m;i++){add(i+n,t,1);add(t,i+n,0);}cout<<EK()<<endl;return 0;
}