0分求调(卑微
查看原帖
0分求调(卑微
363815
LiangE楼主2024/7/29 13:32

rt

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e4+5;
int n1,n2,n3;
int m1,m2;
struct edge{
	int from;
	int to;
	int nxt;
	int c;
}E[2*MAXN];
int head[MAXN],cnt=-1;
int cur[MAXN];
void build(int u,int v){
	E[++cnt].from=u;
	E[cnt].to=v;
	E[cnt].nxt=head[u];
	E[cnt].c=1;
	head[u]=cnt;
	cur[u]=head[u];
}
int dis[MAXN];
bool bfs(){
	memset(dis,-1,sizeof(dis));
	dis[0]=0;
	queue<int>q1;
	q1.push(0);
	while(!q1.empty()){
		int t=q1.front();
		q1.pop();
		for(int i=head[t];i;i=E[i].nxt){
			if(E[i].c==0||dis[E[i].to]!=-1) continue;
			dis[E[i].to]=dis[t]+1;
			q1.push(E[i].to);
		}
	}
	return dis[n1+n1+n2+n3+1]!=-1;
}
int dfs2(int u,int lim){
	if(!lim||u==n1+n1+n2+n3+1) return lim;
	int f=0;
	for(int&i=cur[u];i;i=E[i].nxt){
		int v=E[i].to;
		if(E[i].c&&dis[v]==dis[u]+1){
			int x=dfs2(v,min(lim,E[i].c));
			f+=x;
			lim-=x;
			E[i].c-=x;
			E[i^1].c+=x;
			if(!lim) break;
		}
	}
	return f;
}
int dinic(){
	int ans=0;
	while(bfs()){	
		memcpy(cur,head,sizeof(head));
		ans+=dfs2(0,0x3f3f3f3f);
	}
	return ans;
}
int main(){
	scanf("%d%d%d",&n1,&n2,&n3);
	scanf("%d",&m1);
	for(int i=1;i<=n2;i++){
		build(0,n1+n1+i);
	}
	for(int i=1;i<=m1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		build(v+n1+n1,u);
		build(u,v+n1+n1);
	}
	for(int i=1;i<=n1;i++){
		build(i,n1+i);
	}
	scanf("%d",&m2);
	for(int i=1;i<=m2;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		build(u+n1,v+n1+n1+n2);
		build(v+n1+n1+n2,u+n1);
	}	
	for(int i=1;i<=n3;i++){
		build(i+n1+n1+n2,n1+n1+n2+n3+1);
	}
	cout<<dinic();
	return 0;
}
2024/7/29 13:32
加载中...