那篇博客讲得很清楚，就不再赘述了。在这里贴出一些我犯过的 bug :
/*
bug:1.是q.front()而不是q.back()
2.q需要pop()
3.bfs的条件不是w!=0而是w>0
4.flow不会在同一层被更新，因此不能给flow赋值
5.一次bfs可以dinic多次
6.w数组的索引是e而不是u或者x!!!
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define M 5005
#define inf 0x3f3f3f3f
int tot=1,fir[N],nxt[M],to[M],w[M];
int S,T;
int nl,nr,m,n;
void add(int x,int y,int z){
nxt[++tot]=fir[x];
fir[x]=tot;
to[tot]=y;
w[tot]=z;
}
int dep[N],cur[N],ans;
int firstPoint,lastPoint;
bool bfs(){
for(int i=firstPoint;i<=lastPoint;++i)dep[i]=inf;
queue<int>q;
q.push(S);
dep[S]=0;
while(!q.empty()){
int x=q.front(); //bug #1
q.pop(); //bug #2
for(int e=fir[x];e;e=nxt[e]){
int u=to[e];
if(w[e]<=0||dep[u]!=inf)continue;//bug #3 #6
dep[u]=dep[x]+1;
q.push(u);
if(u==T)return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==T)return flow;
int totf=0;
for(int e=fir[x];e;e=nxt[e]){
int u=to[e];
if(dep[u]!=dep[x]+1||w[e]<=0)continue;
int newf=dinic(u,min(flow,w[e])); //bug #4
if(newf==0){
dep[u]=inf;
continue;
}
w[e]-=newf;
w[e^1]+=newf;
totf+=newf;
flow-=newf;
if(flow==0)return totf;
}
return totf;
}
int main(){
int x,y,z;
scanf("%d %d %d",&m,&nl,&nr);
for(int i=1;i<=m;++i){
scanf("%d %d",&x,&y);
y+=nl;
add(x,y,1);
add(y,x,0);
}
S=nl+nr+1,T=nl+nr+2;
firstPoint=1,lastPoint=T+1;
for(int i=1;i<=nl;++i){
add(S,i,1);
add(i,S,0);
}
for(int i=nl+1;i<S;++i){
add(i,T,1);
add(T,i,0);
}
while(bfs()){
ans+=dinic(S,inf);
}
printf("%d\n",ans);
return 0;
}