代码

#include<bits/stdc++.h>
using namespace std;
const int N=40009;
const int M=40009;
const int inf=1e9;
int s,t;
int dis[N],flow[N],rad[N];
int ans1,ans2;
bool vis[N];
struct edge{
	int to,c;
	int nxt;
}e[M*2];
int hed[N],ecnt;
void add(int l,int r,int c){
	e[ecnt].to=r;
	e[ecnt].c=c;
	e[ecnt].nxt=hed[l];
	hed[l]=ecnt;
	ecnt++;
}
void addd(int l,int r){
	add(l,r,1);
	add(r,l,0);
}
queue<int> q;
bool bfs(){
	for(int i=s;i<=t;i++) vis[i]=0;
	for(int i=s;i<=t;i++) dis[i]=-1;
	for(int i=s;i<=t;i++) rad[i]=hed[i];
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(int i=hed[cur];i;i=e[i].nxt){
			if(dis[e[i].to]==-1&&e[i].c){
				dis[e[i].to]=dis[cur]+1;
				q.push(e[i].to);
			}
		}
	}
	return(dis[t]!=-1);
}
int dfs(int start,int flow){
	int cnt=0;
	vis[start]=1;
	if(start==t) return flow;
	for(int i=rad[start];i&&flow;i=e[i].nxt){
		rad[start]=i;
		if(!vis[e[i].to]&&e[i].c&&dis[e[i].to]==dis[start]+1){
			int ret=dfs(e[i].to,min(flow,e[i].c));
			e[i].c-=ret;
			e[i^1].c+=ret;
			cnt+=ret;
			flow-=ret;
			if(!flow) break;
		}
	}
	vis[start]=0;
	if(!cnt) dis[start]=-1;
	return cnt;
}
int main(){
	int n1,n2,n3,m1,m2;
	cin>>n1>>n2>>n3;
	s=0,t=n1+n1+n2+n3+1;
	for(int i=1;i<=n2;i++) addd(s,i);
	cin>>m1;
	for(int i=0;i<m1;i++){
		int x,y;
		cin>>x>>y;
		addd(y,n2+x);
	}
	for(int i=1;i<=n1;i++) addd(n2+i,n1+n2+i);
	cin>>m2;
	for(int i=0;i<m2;i++){
		int x,y;
		cin>>x>>y;
		addd(n1+n2+x,n1+n1+n2+y);
	}
	for(int i=1;i<=n3;i++) addd(n1+n1+n2+i,t);
	int ans=0;
	while(bfs()){
		ans+=dfs(s,1e9);
	}
	cout<<ans<<endl;
	return 0;
}

记录

感觉像是优化写挂了 大佬们请帮帮我

附上下载来的数据

输入：

5 5 5

7

2 1

4 4

5 4

1 1

5 2

3 1

1 3

7

5 3

2 1

2 5

4 2

3 3

5 2

4 3

标准输出：3 我的输出：2