30分求调
查看原帖
30分求调
999274
CNS_5t0_0r2楼主2025/1/20 14:51
#include<bits/stdc++.h>
using namespace std;
const int N0 = 1e4 + 9,N = N0 << 3,M0 = 2e4 + 9,M = M0 << 3;
int n1,n2,n3,m1,m2,s,t;
int ans;
struct edge{
	int to,cap,nex;
} e[M << 1];
int head[N],ecnt = 1;
int head2[N];//分层图的表头 
void addedge(int u,int v,int c){
	ecnt++;
	e[ecnt] = (edge){v,c,head[u]};
	head[u] = ecnt;
}
queue<int> que;
int dep[N];//层次 
bool bfs(){//构造分层图 
	memset(dep,0,sizeof dep);
	que.push(s);
	dep[s] = 1;
	head2[s] = head[s];
	while(!que.empty()){
		int u = que.front();
		que.pop();
		for(int i = head[u];i;i = e[i].nex){
			int v = e[i].to,c = e[i].cap;
			if(dep[v] || !c)
				continue;
			head2[v] = head[v];
			dep[v] = dep[u] + 1;
			que.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int flow){//在分层图上增广 
	if(u == t)
		return flow;
	int rest = flow,tmp;
	for(int i = head2[u];i && rest;i = e[i].nex){
		head2[u] = i;
		int v = e[i].to,c = e[i].cap;
		if(dep[v] != dep[u] + 1 || !c)
			continue;
		tmp = dfs(v,min(rest,c));
		if(!tmp)
			dep[v] = 0;//当无法从v 增广时,将v从分层图中删除
		e[i].cap -= tmp;
		e[i ^ 1].cap += tmp;
		rest -= tmp;
	}
	return flow - rest;//流到u的流量减去流出u后剩余的流量就是流到汇点的流量
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n1 >> n2 >> n3;
	cin >> m1;
	for(int i = 1;i <= m1;i++){
		int u,v;
		cin >> u >> v;
		addedge(v,u + n2,1);
		addedge(u + n2,v,0);
	}
	for(int i = 1;i <= n1;i++){
		addedge(i + n2,i + n1 + n2,1);
		addedge(i + n1 + n2,i + n1,0);
	}
	cin >> m2; 
	for(int i = 1;i <= m2;i++){
		int u,v;
		cin >> u >> v;
		addedge(u + n1 + n2,v + n1 + n1 + n2,1);
		addedge(v + n1 + n1 + n2,u + n1 + n2,1);
	}
	s = 0;t = n1 + n1 + n2 + n3 + 1;
	for(int i = 1;i <= n2;i++){
		addedge(s,i,1);
		addedge(i,s,0);
	}
	for(int i = n1 + n1 + n2 + 1;i <= n1 + n1 + n2 + n3;i++){
		addedge(i,t,1);
		addedge(t,i,0);
	}
	int flow = 0;
	while(bfs())
		while(flow = dfs(s,n2 + 1))
			ans += flow;
	cout << ans;
	return 0;
}
2025/1/20 14:51
加载中...