社区讨论

为什么tot的值从1改成0就会炸

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@lo127xfz
此快照首次捕获于
2023/10/22 14:00
2 年前
此快照最后确认于
2023/11/02 13:29
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std;
struct node{
	int nxt;
	int to;
	int val;
}e[10010];
int tot=0,now[210],head[210],dis[210];
int n,m,s,t;
void add(int u,int v,int val)
{
	e[++tot].to=v;
	e[tot].val=val;
	e[tot].nxt=head[u];
	head[u]=tot;
	
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].nxt=head[v];
	head[v]=tot;
}
/*inline void add(int u,int v,long long w) {
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].nxt=head[u];
	head[u]=tot;
	
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].nxt=head[v];
	head[v]=tot;
}*/
int bfs()
{
	for(int i=1;i<=n;i++)dis[i]=inf;
	queue<int > q;
	q.push(s);
	dis[s]=0;
	now[s]=head[s];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(e[i].val>0&&dis[v]==inf)
			{
				q.push(v);
				dis[v]=dis[x]+1;
				now[v]=head[v];
				if(v==t)return 1;
			}
		}
	}
	return 0;
}


int dfs(int x,int sum)
{
	if(x==t)return sum;
	int k,res=0;
	for(int i=now[x];i&&sum;i=e[i].nxt)
	{
		now[x]=i;
		int v=e[i].to;
		if(e[i].val>0&&(dis[v]==dis[x]+1)) {
			k=dfs(v,min(sum,e[i].val));
			if(k==0) dis[v]=inf;
			e[i].val-=k;
			e[i^1].val+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int ans=0;
signed main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int u,v,e;
		cin>>u>>v>>e;
		add(u,v,e);
	}
	while(bfs())
	{
		ans+=dfs(s,inf);
	}
	cout<<ans;
    return 0;
}

++tot不应该是先加再计算吗,那e[1]不是会空出来吗

回复

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

正在加载回复...