社区讨论

昨晚和今早一共De了好几个小时的Bug了,求dalao查错

P1231教辅的组成参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi86koac
此快照首次捕获于
2025/11/21 09:27
4 个月前
此快照最后确认于
2025/11/21 09:27
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+c-48,c=getchar();
	return x;
}
inline int Min(int a,int b){
	return a<b?a:b;
}
const int N=4e4+5,M=2e5+5,INF=2e9;
struct node{
	int next,to,flow;
}edge[M];
int dep[N],head[N],cnt[N];
int n1,n2,n3,m,s,t,tot=1;
inline void add(int x,int y,int flow){
	edge[++tot].next=head[x];
	edge[tot].to=y;
	edge[tot].flow=flow;
	head[x]=tot;
}
inline bool bfs(){
	memset(dep,-1,sizeof(dep));
	queue<int>q;
	dep[s]=0;
	for(int i=s;i<=t;++i)cnt[i]=head[i];
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=edge[i].next){
			int nxt=edge[i].to;
			if(dep[nxt]==-1&&edge[i].flow){
				dep[nxt]=dep[now]+1;
				q.push(nxt);
			}
		}
	}
	if(dep[t]==-1)return false;
	return true;
}
int dfs(int now,int minn){
	if(now==t||!minn)return minn;
	int Flow=0,f;
	for(int i=cnt[now];i;i=edge[i].next){
		int nxt=edge[i].to;
		cnt[now]=i;
		if(dep[nxt]==dep[now]+1&&(f=dfs(nxt,Min(minn,edge[i].flow)))){
			Flow+=f;
			minn-=f;
			edge[i].flow-=f;
			edge[i^1].flow+=f;
			if(!minn)break;
		}
	}
	return Flow;
}
int main(){
	n1=read();n2=read();n3=read();
	t=n1+n2+n3+1;
	m=read();
	for(int i=1;i<=n2;++i){
		add(s,i,1);
		add(i,s,0);
	}
	int x,y;
	while(m--){
		x=read()+n2;y=read();
		add(x,y,0);
		add(y,x,1);
	}
	m=read();
	while(m--){
		x=read()+n2;y=read()+n1+n2;
		add(x,y,1);
		add(y,x,0);
	}
	for(int i=n1+n2+1;i<t;++i){
		add(t,i,0);
		add(i,t,1);
	}
	int ans=0;
	while(bfs())
		ans+=dfs(s,INF);
	printf("%d",ans);
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...