试过ek模板了应该不是模板部分有问题。网络流建模方面的思路是:建立一个源点,连接所有左边的点,建议一个汇点,将所有右边的点与其连接。
刚学网络流,而且特别菜,麻烦各位大佬指正错误。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int inf=0x3f3f3f3f;
int a,b,k,ans,s,t;
struct EDGE{
int to,next,w;
}e[N];
int head[N],cnt=1;
void add(int x,int y,int z){
++cnt;
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int pre[N],v[N],incf[N];
bool bfs(){
memset(v,0,sizeof(v));
queue<int> q;
q.push(s);
v[s]=1;
incf[s]=inf;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].next){
if(e[i].w!=0){
int y=e[i].to;
if(v[y]) continue;
incf[y]=min(incf[x],e[i].w);
pre[y]=i;
q.push(y),v[y]=1;
if(y==t) return 1;
}
}
}
return 0;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
e[i].w-=incf[t];
e[i^1].w+=incf[t];
x=e[i^1].to;
}
ans+=incf[t];
}
int main(){
scanf("%d%d%d",&a,&b,&k);
s=0,t=a+b+1;
for(int i=1;i<=a;i++){
add(s,i,1),add(i,s,0);
}
for(int i=a+1;i<=a+b;i++){
add(i,t,1),add(t,i,0);
}
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
y+=a;
add(x,y,1);
add(y,x,0);
}
while(bfs()){
update();
}
printf("%d",ans);
return 0;
}