EK 30分求助
查看原帖
EK 30分求助
251870
LazYQwQ楼主2022/1/3 13:08
#include<bits/stdc++.h>
using namespace std;
#define N 201000
#define M 200001
int n,p,q,m1,m2;
int s,t,tot;
int head[N],ver[M],edge[M],nxt[M];
void add(int x,int y,int z) {
	ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
	ver[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
int maxflow,incf[N],pre[N];
bool vis[N];

bool bfs() {
    for(int i=1;i<=N;i++)vis[i]=0;
	queue<int> Q;
	Q.push(s),vis[s]=1,incf[s]=2147483637;
	while(!Q.empty()) {
		int x=Q.front();
		Q.pop();
		for(int i=head[x]; i; i=nxt[i])
			if(edge[i]) {
				int y=ver[i];
				if(vis[y])continue;
				incf[y]=min(incf[x],edge[i]),pre[y]=i;
				vis[y]=1;
				if(y==t)return 1;
				Q.push(y);
			}
	}
	return 0;
}
void update() {
	int x=t;
	while(x!=s) {
		int i=pre[x];
		edge[i]-=incf[t];
		edge[i^1]+=incf[t];
		x=ver[i^1];
	}
	maxflow+=incf[t];
}
int main() {
	tot=1;
	cin>>n>>p>>q;
	s=0;
	t=2*n+p+q+1;
	for(int i=1;i<=p;i++)add(s,i,1);
	cin>>m1;
	int x,y;
	for (int i=1; i<=m1; i++) {
		cin>>x>>y;
		add(y,x+p,1);
	}
	for(int i=1;i<=n;i++)add(i+p,i+p+n,1);
	cin>>m2;
	for (int i=1; i<=m2; i++) {
		cin>>x>>y;
		add(x+n+p,y+2*n+p,1);
	}
	for (int i=1; i<=q; i++) add(i+2*n+p,t,1);
	while(bfs()){
		update();
	}
	cout<<maxflow;
	return 0;
}
2022/1/3 13:08
加载中...