Luogu P3381 (模板题) 最小费用最大流

<题目链接>

题目大意:

给定一张图,给定条边的容量和单位流量费用,并且给定源点和汇点。问你从源点到汇点的最带流和在流量最大的情况下的最小费用。

解题分析:

最小费用最大流果题。

下面的是MCMF的模板。想学ZKW费用流最小费用流的原始对偶 (Primal-Dual) 算法的同学,可以看看ZKW本人(Orz)的讲解  >>>

#include <bits/stdc++.h>
using namespace std;
int h[],d[],used[],que[],last[];
int cnt=,INF=0x3f3f3f3f,ans1=,ans2=;
#define clr(a,b) memset(a,b,sizeof(a))
template<typename T>
inline void read(T&x){
x=;int f=;char c=getchar();
while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }
while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }
x*=f;
}
struct Edge{ int to,cap,cost,next; }e[]; inline void add(int from,int to,int c1,int c2){
e[++cnt]=(Edge){to,c1,c2,h[from]};h[from]=cnt;
e[++cnt]=(Edge){from,,-c2,h[to]};h[to]=cnt;
}
bool spfa(int s,int t){ //slf优化
clr(last,);clr(d,INF);clr(used,);
int head,tail;
tail=head=;
que[tail]=s;used[s]=;d[s]=;
while(head<=tail){ //数组模拟双端队列
int x=que[head++];
for(int i=h[x];i;i=e[i].next){
if(e[i].cap&&d[x]+e[i].cost<d[e[i].to]){ //如果这条路上还有残余容量,就更新其费用,让其费用最小
d[e[i].to]=d[x]+e[i].cost;
last[e[i].to]=i; //记录这个点的最大费用所对应的前一条边的编号
if(!used[e[i].to]){
if(d[e[i].to]<d[que[head]])que[--head]=e[i].to; //如果这个点的费用小于队列的头部的话,就将它塞入队列头部
else que[++tail]=e[i].to; //否则的话,塞入队尾
used[e[i].to]=;
}
}
}
used[x]=;
}
return d[t]!=INF;
}
void MCMF(int t){
int minn=INF;
for(int i=last[t];i;i=last[e[i^].to])minn=min(minn,e[i].cap); //沿着那个记录的反向增广路径更新这条路上的最小容量
ans1+=minn;
for(int i=last[t];i;i=last[e[i^].to]){
ans2+=e[i].cost*minn; //费用=单位流量费用*流量
e[i].cap-=minn; //正向边容量-=minn
e[i^].cap+=minn; //反向边容量+=minn
}
}
int main(){
int n,m,s,t;
read(n);read(m);read(s);read(t);
for(int i=;i<=m;i++){
int x,y,w,f;read(x);read(y);read(w);read(f);
add(x,y,w,f);
}
while(spfa(s,t))MCMF(t);
printf("%d %d\n",ans1,ans2);
}
上一篇:VCL界面控件DevExpress VCL Controls发布v18.2.7|附下载


下一篇:VCL界面控件DevExpress VCL Controls发布v18.2.4|附下载