#网络流，费用流，SLF优化，SPFA，zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容

本文主要是介绍#网络流，费用流，SLF优化，SPFA，zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有两个问题，首先求1到 $n$ 的最大流（不解释了），然后求1到n使最大流扩展 $k$ 的费用，每扩展一个最大流，扩展一次边的费用

分析

当然如何做第二个问题，可以重新建一个汇点流量是最大流 $+ k$ ，费用为0，并且原来的边再建一次从 $u$ 到 $v$ ，费用为该边的费用，流量无限跑一次最大流，then就讲完了

代码

    #include <cstdio>#include <cstring>#include <queue>#define rr registerusing namespace std;struct node{int y,w,f,next;}e[20005];int n,k=1,dis[1003],ls[1003],ans; bool v[1003];inline int in(){rr int ans=0; rr char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();return ans;}inline void add(int x,int y,int w,int f){e[++k]=(node){y,w,f,ls[x]}; ls[x]=k;e[++k]=(node){x,0,-f,ls[y]}; ls[y]=k;}inline int spfa(){//反向跑spfamemset(v,0,sizeof(v)); memset(dis,127/3,sizeof(dis));dis[n]=0; v[n]=1; rr deque<int>q; q.push_back(n);while (q.size()){rr int x=q.front(); q.pop_front();for (rr int i=ls[x];i;i=e[i].next)if (e[i^1].w&&dis[e[i].y]>dis[x]-e[i].f){dis[e[i].y]=dis[x]-e[i].f;if (!v[e[i].y]){v[e[i].y]=1;if (q.size()&&dis[e[i].y]<dis[q.front()]) q.push_front(e[i].y); else q.push_back(e[i].y);}}v[x]=0;}return dis[n+1]<707406378;}inline int dfs(int x,int now){//长得很像dinicif (x==n) {v[n]=1; return now;}rr int rest=0,f; v[x]=1;for (rr int i=ls[x];i;i=e[i].next)if (!v[e[i].y]&&e[i].w>0&&dis[e[i].y]+e[i].f==dis[x]){rest+=(f=dfs(e[i].y,min(e[i].w,now-rest)));if (f) ans+=e[i].f*f,e[i].w-=f,e[i^1].w+=f;if (now==rest) return now;}return rest;}inline int zkw(){int ans=0;while (spfa()){do{memset(v,0,sizeof(v));ans+=dfs(n+1,1e9);}while (v[n]);}return ans;}int main(){n=in(); rr int m=in(),t=in();rr int w[m+1],f[m+1],t1;for (rr int i=1;i<=m;i++){rr int x=in(),y=in();w[i]=in(); f[i]=in();add(x,y,w[i],0);}add(n+1,1,2333333,0);printf("%d ",t1=zkw()); t+=t1;e[k].w=0; e[k^1].w=t;//超级源点for (rr int i=1;i<=m;i++) e[i<<1].w=w[i],e[i<<1|1].w=0;//重新建图for (rr int i=1;i<=m;i++) add(e[i<<1|1].y,e[i<<1].y,23333333,f[i]);//无限流量zkw(); return !printf("%d",ans);}