rt,拍好久拍不出来,应输出 230 输出 231,求大佬帮帮 T T。
#include<queue>
#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int N=10005,M=5e5+5,inf=1e11;
struct Edge{
int l,w,nxt;
}edges[M<<1];
int n1,n2,m,s,t,tt=1,head[N],cur[N],vu[N];
void add_edge(int f,int l,int w){
edges[++tt]={l,w,head[f]};
head[f]=tt;
}
bool bfs(){
memset(vu,0,sizeof(vu));
queue<int> qo;
qo.push(s),vu[s]=1;
while(!qo.empty()){
int x=qo.front();qo.pop();
if(x==t) return 1;
for(int i=head[x];i;i=edges[i].nxt){
int l=edges[i].l,w=edges[i].w;
if(vu[l]||!w) continue;
vu[l]=vu[x]+1;qo.push(l);
}
}
return 0;
}
int dfs(int x,int mf,int an=0){
if(x==t) return mf;
for(int i=cur[x];i;i=edges[i].nxt){
cur[x]=i;
int l=edges[i].l,w=edges[i].w;
if(vu[l]!=vu[x]+1||!w) continue;
int f=min(mf,w);f=dfs(l,f);
mf-=f,an+=f;
edges[i].w-=f,edges[i^1].w+=f;
if(!mf) break;
}
if(!an) vu[x]=0;
return an;
}
int Dinic(int ans=0){
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n1>>n2>>m;int f,l;
s=n1+n2+1,t=n1+n2+2;
for(int i=1;i<=m;i++){
cin>>f>>l;l=n1+l;
add_edge(f,l,1);add_edge(l,f,0);
add_edge(l,f,1);add_edge(f,l,0);
}
for(int i=1;i<=n1;i++){
add_edge(s,i,1);
add_edge(i,s,0);
}
for(int i=1;i<=n2;i++){
add_edge(i+n1,t,1);
add_edge(t,i+n1,0);
}
cout<<Dinic();
return 0;
}