2023年7月30日发(作者：)

⽹络流--费⽤流Ek算法讲解前⼀篇博客写的是最⼤流。先简要说⼀下思路，⽅便下⾯的讲解。最⼤流求解是先跑⼀遍bfs，把每个点定义⼀个深度,跑dfs的同时连接⼀条反向边⽅便反悔，避免不必要的时间。现在说⼀下费⽤流。费⽤流的全称是最⼩费⽤最⼤流(或最⼤费⽤最⼤流)，保证最⼩费⽤的情况下跑最⼤流。最⼩费⽤？BFS -> SPFA成功解决。我们不需要再给每个点定义深度，⽽是直接把费⽤当成边权求⼀遍到原点的最短路。但是，流量的反向边初始值为0，费⽤是0吗？显然不是，因为如果不需要⾛这条边显然是不需要费⽤的，所以正向边+反向边的费⽤为0.显然费⽤为-cost。下⼀个问题，如果我们找到了最短路，如何寻找路径把费⽤累加并更改流量？SPFA解决！之后我们当前dfs的流量需要⽤⼀个数组存起来，⽽不是⼀个变量。之后就没什么了，不会的问我。题⽬描述如题，给出⼀个⽹络图，以及其源点和汇点，每条边已知其最⼤流量和单位流量费⽤，求出其⽹络最⼤流和在最⼤流情况下的最⼩费⽤。输⼊格式： 第⼀⾏包含四个正整数N、M、S、T，分别表⽰点的个数、有向边的个数、源点序号、汇点序号。接下来M⾏每⾏包含四个正整数ui、vi、wi、fi，表⽰第i条有向边从ui出发，到达vi，边权为wi（即该边最⼤流量为wi），单位流量的费⽤为fi。输出格式： ⼀⾏，包含两个整数，依次为最⼤流量和在最⼤流量情况下的最⼩费⽤。样例输⼊：4 5 4 34 2 30 24 3 20 32 3 20 12 1 30 91 3 40 5样例输出：50 280code：#include#include#include#includeusing namespace std;#define N 100000int n,m,S,T;int f[N];int now[N];int head[N];int to[N];int val[N];int nex[N];int cost[N];int idx=1;int inq[N];int pre[N];int maxflow;int ans;int a,b,c,d;int nowflow[N];void addedge(int a,int b,int c,int d){ nex[++idx]=head[a]; head[a]=idx; to[idx]=b; val[idx]=c; cost[idx]=d;}bool spfa(int S,int T){ queue q; memset(f,0x3f,sizeof(f)); memset(inq,0,sizeof(inq)); memset(nowflow,0x3f,sizeof(nowflow)); (S); f[S]=0; inq[S]=1; //cost[S]=1<<30; while(!()) { int x=(); inq[x]=0; (); for(int i=head[x];i;i=nex[i]) { if(val[i]>0&&f[to[i]]>f[x]+cost[i]) { f[to[i]]=f[x]+cost[i]; nowflow[to[i]]=min(nowflow[x],val[i]); pre[to[i]]=i; if(!inq[to[i]]) { inq[to[i]]=1; (to[i]); } } } } if(f[T]>=0x3f3f3f3f) return 0; return 1;}void EK(){ int x=T; while(x!=S) { int i=pre[x]; val[i]-=nowflow[T]; val[i^1]+=nowflow[T]; x=to[i^1]; } maxflow+=nowflow[T]; ans+=f[T]*nowflow[T];}int main(){ scanf("%d%d%d%d",&n,&m,&S,&T); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); addedge(a,b,c,d); addedge(b,a,0,-d); } while(spfa(S,T)) EK(); printf("%d %d",maxflow,ans);}