社区讨论
最小费用最大流模板题求助
P3381【模板】最小费用最大流参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6gqxqr
- 此快照首次捕获于
- 2025/11/20 04:36 4 个月前
- 此快照最后确认于
- 2025/11/20 04:36 4 个月前
求助!
Dinic+Spfa最小费用最大流wa了2 9 10 三个点,请个位大犇帮忙看一下!!!
CPP#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#define For(i,a,b) for((i)=(a);(i)<=(b);++(i))
#define Forward(i,a,b) for((i)=(a);(i)>=(b);--(i))
using namespace std;
const int inf=0xFFFFFFF;
inline void read(int &x)
{
int s=0,f=1;
char k=getchar();
while(!isdigit(k)&&k!='-')k=getchar();
if(k=='-')
{
f=-1;
k=getchar();
}
while(isdigit(k))
{
s=(s<<3)+(s<<1)+(k^'0');
k=getchar();
}
x=s*f;
}
struct edge
{
int v,w,next,f;
}p[100000+100];
int n,a[5000+100],m,he[5000+100],s,t,e=1,level[5000+100];
long long fee;
bool vis[5000+100];
void add(int u,int v,int w,int f)
{
p[++e].v=v;
p[e].w=w;
p[e].next=he[u];
p[e].f=f;
he[u]=e;
}
queue<int>G;
bool spfa(int s)
{
fill(level+1,level+n+1,inf);
memset(vis,0,sizeof(vis));
level[s]=1;
G.push(s);
vis[s]=true;
while(!G.empty())
{
int u=G.front(),v=he[u];
G.pop();
while(v)
{
if(p[v].w&&level[p[v].v]>level[u]+p[v].f)
{
level[p[v].v]=level[u]+p[v].f;
if(!vis[p[v].v])
{
vis[p[v].v]=true;
G.push(p[v].v);
}
}
v=p[v].next;
}
vis[u]=false;
}
return level[t]!=inf;
}
int dfs(int x,int flow)
{
if(x==t||!flow)return flow;
int v=he[x],sum=0;
while(v)
{
if(p[v].w&&level[p[v].v]==level[x]+p[v].f)
{
int f=dfs(p[v].v,min(flow,p[v].w));
fee+=(long long)p[v].f*(long long)f;
flow-=f;
p[v].w-=f;
p[v^1].w+=f;
sum+=f;
}
v=p[v].next;
}
return sum;
}
int Dinic(void)
{
int ans=0;
while(spfa(s))ans+=dfs(s,inf);
return ans;
}
int main(void)
{
int i,j,u,v,w,f;
read(n);
read(m);
read(s);
read(t);
For(i,1,m)
{
read(u);
read(v);
read(w);
read(f);
add(u,v,w,f);
add(v,u,0,0);
}
printf("%d",Dinic());
printf(" %lld\n",fee);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...