给出一个容量网络, 那他的最大流一定是一个定值(即使是有多个一样的最大值). 所以我们从开始的可行流开始增广时, 最终的增广量是一定的. 所以为了满足最小费用我们只需要每次找最小费用的增广路即可, 直到流量为最大值. 这个问题仅仅是在求增广路时先考虑费用最小的增广路, 其他思想和 EK 思想一样.
我们学过 SPFA 求最短路算法(bellman-ford 的队列优化), 所以我们将弧的费用看做是路径长度, 即可转化为求最短路的问题了. 只需要所走的最短路满足两个条件即可: 1 可增广 cap> flow,2 路径变短 d[v]>d[u]+cost<u,v>
网络流 (六) 最小费用最大流问题 https://www.cnblogs.com/fzl194/p/8859308.html
其实就是把 dinic 中的 bfs 换成 spfa,dfs 换成回溯修改剩余网络和答案的过程.
算法流程:
用 spfa 寻找每条边上费用之和最小的增广路, 沿途找到最小流量, 把经过的点记录下来.
把最小费用增广路上的边剩余流量修改了
回到 1
注意, 反边费用为其对应边的相反数
ps: 有个很神奇的地方没搞懂: 一开始我忘记打 spfa 里面 "bz[x]=0;" 这一句, 结果算出的最大流比答案大?!!
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- struct qy
- {
- int x,y,flow,cost;
- };
- int n,m,S,T,i,j,x,y,z1,z2,tot,maxflow,mincost;
- qy l[200005];
- int next[200005],last[200005];
- int dis[5005],flow[5005],from[5005],bz[5005];
- int list[200005],head,tail;
- void insert(int x,int y,int z1,int z2)
- {
- tot++;
- l[tot].x=x;
- l[tot].y=y;
- l[tot].flow=z1;
- l[tot].cost=z2;
- next[tot]=last[x];
- last[x]=tot;
- }
- int spfa()
- {
- memset(bz,0,sizeof(bz));
- memset(flow,0,sizeof(flow));
- memset(dis,120,sizeof(dis));
- list[1]=S;bz[S]=1;head=0;tail=1;dis[S]=0;flow[S]=1000000000;
- while (head<tail)
- {
- int x=list[++head];
- for (int i=last[x];i>=1;i=next[i])
- {
- int y=l[i].y;
- if ((l[i].flow>0)&&(dis[y]>dis[x]+l[i].cost))
- {
- dis[y]=dis[x]+l[i].cost;
- from[y]=i;
- flow[y]=min(flow[x],l[i].flow);
- if (!bz[y])
- {
- bz[y]=1;list[++tail]=y;
- }
- }
- }
- bz[x]=0;
- }
- if (flow[T]>0) return 1;
- else return 0;
- }
- void mfmc()
- {
- while (spfa())
- {
- maxflow+=flow[T];
- mincost+=flow[T]*dis[T];
- for (int x=T;x!=S;x=l[from[x]].x)
- {
- l[from[x]].flow-=flow[T];
- l[from[x]^1].flow+=flow[T];
- }
- }
- }
- int main()
- {
- freopen("read.in","r",stdin);
- scanf("%d%d%d%d",&n,&m,&S,&T);
- tot=1;
- for (i=1;i<=m;i++)
- {
- scanf("%d%d%d%d",&x,&y,&z1,&z2);
- insert(x,y,z1,z2);
- insert(y,x,0,-z2);
- }
- mfmc();
- printf("%d %d",maxflow,mincost);
- }
来源: http://www.bubuko.com/infodetail-3116659.html