最大流错5,6,7个点求助
#include<bits/stdc++.h>
using namespace std;
const int maxn =510000,maxm = 5201000,INF = 1e8;
int n,m,e1,S,T;
int d[maxn],f[maxm],cur[maxn];
int nxt[maxm],head[maxn],e[maxm],cnt=1;
void add(int a,int b,int c){
e[cnt] = b , f[cnt] = c, nxt[cnt] = head[a] , head[a] =cnt++;
e[cnt] = a , f[cnt] = 0, nxt[cnt] = head[b] , head[b] =cnt++;
}
// bfs 寻找增广路的同时建残存网络
bool bfs(){
memset(d,-1,sizeof (d));
queue<int> q;
q.push(S),d[S]=0,cur[S]=head[S];
while(q.size()){
int L=q.front(); q.pop();
for(int i=head[L];i;i=nxt[i]){
int ver = e[i];
if(d[ver] == -1&& f[i]) {
d[ver] = d[L] + 1;
cur[ver] = head[ver];
if(ver==T) return true;
q.push(ver);
}
}
}
return false;
}
//find(当前节点,在节点之前最大流量) 返回从N节点到T的最大流量
int find(int n,int limit){
if(n == T) return limit;
int flow =0;
for(int i=head[n];i && flow < limit;i=nxt[i]){ //搞我心态 ~i
cur[n] = i;
int ver = e[i];
if(d[ver] == d[n] + 1 && f[i]){
int t = find(ver , min(f[i],limit-flow));
if(!t) d[ver] = -1;
f[i] -= t , f[i ^ 1] += t, flow += t;
}
}
return flow;
}
//dinic 不断找增广路径,直至不能找,维护残存网路,返回最大流
int dinic(){
int flow=0,res=0;
while(bfs()) while((flow = find(S,INF))) {res+=flow;}
return res;
}
int main (){
cin>>n>>m>>e1;
S=0 ,T=n+m+1;
for(int i=1;i<=n;i++) add(S,i,1);
for(int i=n+1;i<=n+m;i++) add(i,T,1);
int i,j;
for(int i=1;i<=e1;i++) {cin>>i>>j;add(i,j+n,1);}
cout<<dinic()<<endl;
return 0;
}