社区讨论

蒟蒻刚学网络流,求大佬查错

P3376【模板】网络最大流参与者 7已保存回复 13

讨论操作

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

当前回复
13 条
当前快照
1 份
快照标识符
@mi7xxmhv
此快照首次捕获于
2025/11/21 05:25
4 个月前
此快照最后确认于
2025/11/21 06:40
4 个月前
查看原帖
RT,我用的Dinic
CPP
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,ss,tt;
int h[200005],cnt=0;
int num[200005];//num记录点的层 
struct node{int nx,to,v;}w[200005];
void AddEdge(int x,int y,int z){w[++cnt].to=y;w[cnt].v=z;w[cnt].nx=h[x];h[x]=cnt;}
int BFS(int s,int t)
{
	queue<int>q;
	memset(num,-1,sizeof(num));
	num[s]=0;//初始化
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		if(x==t)return 1;
		for(int i=h[x];i;i=w[i].nx)
		{
			int y=w[i].to;
			if(num[y]==-1&&w[i].v>0){num[y]=num[x]+1;q.push(y);}
		}
	}
	return 0;
}
int DFS(int x,int t,int maxx)
{
	int ans=0,d=0;
	if(x==t)return maxx;
	for(int i=h[x];i;i=w[i].nx)
	{
		int y=w[i].to;
		if(w[i].v>0&&num[y]==num[x]+1)//必须按层序走才能保证最短路
		{
			d=DFS(y,min(w[i].v,maxx),t);
			w[i].v-=d;
			w[i^1].v+=d;//更新正向弧和反向弧的容量
			ans+=d;
			maxx-=d;
			if(maxx==0)return ans;
		}
	}
	return ans;
}
void Dinic()
{
	int ans=0;
	while(BFS(ss,tt))ans+=DFS(ss,tt,0x3f3f3f3f);
	printf("%d",ans);
}
int main()
{
	scanf("%d %d %d %d",&n,&m,&ss,&tt);
	for(int i=1;i<=m;i++)
	{
		int xx,yy,zz;
		scanf("%d %d %d",&xx,&yy,&zz);
		AddEdge(xx,yy,zz);
		AddEdge(yy,xx,0);
	}
	Dinic();
	return 0;
}


回复

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

正在加载回复...