社区讨论
萌新求助——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 条回复,欢迎继续交流。
正在加载回复...