洛谷：P1231 教辅的组成

最新推荐文章于 2025-06-01 11:36:00 发布

冈易玩家

最新推荐文章于 2025-06-01 11:36:00 发布

阅读量129

点赞数

分类专栏：无聊人士编文章标签：图论深度优先算法数据结构 c++

本文链接：https://blog.csdn.net/Darwin1216/article/details/142022338

版权

无聊人士编专栏收录该内容

59 篇文章

订阅专栏

*转载于该题题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=4e4+5,M=1e6+5;
int n1,n2,n3,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int p,int x) {
	switch(p) {
		case 1: return x;
		case 2: return n2+x;
		case 3: return n2+n1+x;
		case 4: return n2+n1+n1+x;
	}
}
void add(int u,int v,int w) {
	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
	add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
	memset(dep,0,sizeof(dep));
	memcpy(cnr,lnk,sizeof(lnk));
	std::queue<int> q;
	q.push(s),dep[s]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=lnk[u];i;i=nxt[i]) {
			int v=ter[i];
			if(!dep[v]&&val[i]) dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int t,int flow) {
	if(u==t) return flow;
	int ans=0;
	for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
		cnr[u]=i;
		int v=ter[i];
		if(val[i]&&dep[v]==dep[u]+1) {
			int x=dfs(v,t,std::min(val[i],flow-ans));
			if(x) val[i]-=x,val[i^1]+=x,ans+=x;
		}
	}
	if(ans<flow) dep[u]=-1;
	return ans;
}
int dinic(int s,int t) {
	int ans=0;
	while(bfs(s,t)) {
		int x;
		while((x=dfs(s,t,1<<30))) ans+=x;
	}
	return ans;
}
int main() {
	scanf("%d%d%d",&n1,&n2,&n3);
	for(scanf("%d",&m);m--;) {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(id(1,v),id(2,u),1);
	}
	for(scanf("%d",&m);m--;) {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(id(3,u),id(4,v),1);
	}
	for(int i=1;i<=n1;++i) addedge(id(2,i),id(3,i),1);
	int S=0,T=n2+n1+n1+n3+1;
	for(int i=1;i<=n2;++i) addedge(S,id(1,i),1);
	for(int i=1;i<=n3;++i) addedge(id(4,i),T,1);
	printf("%d\n",dinic(S,T));
	return 0;
}