社区讨论

萌新求助——dinic+SPFA后4个点WA

P3381【模板】最小费用最大流参与者 3已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lockf5o2
此快照首次捕获于
2023/10/30 15:15
2 年前
此快照最后确认于
2023/11/05 02:28
2 年前
查看原帖
rt
萌新需要大佬的帮助,谢谢谢谢。
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
queue<int> line;
struct side
{
	int to,next;
	ll weight,flow;
}a[200001];
int s[5001],cur[5001],dep[5001],cnt=1,n,m,f,t;
ll dis[5001],ans,an;
inline void mem(int q,int w,ll e,ll r)
{
	a[++cnt].to=w;
	a[cnt].next=s[q];
	s[q]=cnt;
	a[cnt].weight=e;
	a[cnt].flow=r;
	return;
}
inline bool bfs()
{
	memset(dep,0,sizeof(dep));
	memset(dis,0x7f7f7f,sizeof(dis));
	memcpy(cur,s,sizeof(s));
	while(!line.empty())
		line.pop();
	dep[f]=f;
	dis[f]=0;
	line.push(f);
	while(!line.empty())
	{
		int x=line.front();
		line.pop();
		int w=s[x];
		while(w)
		{
			if(dis[a[w].to]>dis[x]+a[w].weight&&a[w].flow!=0)
			{
				dis[a[w].to]=dis[x]+a[w].weight;
				dep[a[w].to]=x;
				line.push(a[w].to);
			}
			w=a[w].next;
		}
	}
	if(dep[t])
		return 1;
	return 0;
}
inline ll dfs(int x,ll fl)
{
	if(x==t)
		return fl;
	ll re=fl;
	int w=cur[x];
	while(w&&re)
	{
		cur[x]=w;
		if(dep[a[w].to]==x&&a[w].flow!=0)
		{
			ll z=dfs(a[w].to,min(re,a[w].flow));
			ans+=z*a[w].weight;
			a[w].flow-=z;
			a[w^1].flow+=z;
			re-=z;
		}
		w=a[w].next;
	}
	return fl-re;
}
int main()
{
	std::ios::sync_with_stdio(0);
	cin>>n>>m>>f>>t;
	for(int i=1;i<=m;i++)
	{
		int q,w;
		ll e,r;
		cin>>q>>w>>e>>r;
		mem(q,w,r,e);
		mem(w,q,r,0);
	}
	while(bfs())
		an+=dfs(f,0x7f7f7f);
	cout<<an<<" "<<ans;
	return 0;
}

回复

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

正在加载回复...