洛谷P2604 最大流+最小费用最大流

题目链接：https://www.luogu.org/problem/P2604

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

解题思路：

1.对于1，直接跑一遍最大流即可，费用设为 0 。

2.对于2，在跑完最大流后的残留网络上加边，对每条边加上容量为 inf，费用为边的扩容费用。这样保证费用是正确的，为了保证扩容为k，加一个源点0，容量为k，费用为 0 ，连向1点。跑最小费用（0，n）即可。

3.思考为什么可以在残留网络上加边，因为边的费用不是单位流量费用，而是扩容费用。对一条已经满流的边扩容即可增加其他未满流的边的流量，这时其他边的费用是0，因为并没有扩容。在其他边也满流之后，扩容才需要费用，也才会用到所加的inf的边（因为残留网络

上费用为0，会优先用）

代码：

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<queue>
  4 #include<algorithm>
  5 #define mem(a, b) memset(a, b, sizeof(a))
  6 using namespace std;
  7 const int MAXM = 5010;
  8 const int MAXN = 5000;
  9 const int inf = 0x3f3f3f3f;
 10 
 11 int n, m, k; //n个点 m条有向边, 扩容k
 12 queue<int> Q;
 13 int dep[MAXN], last[MAXN], pre[MAXN], dis[MAXN], flow[MAXN], vis[MAXN];
 14 
 15 struct Node
 16 {
 17     int a, b, c, d;
 18 }no[MAXM];
 19 int tot;
 20 
 21 struct Edge
 22 {
 23     int to, next, flow, dis;
 24 }edge[5 * MAXN];
 25 int head[MAXN], cnt;
 26 
 27 void add(int a, int b, int c, int d)
 28 {
 29     edge[++ cnt].to = b;
 30     edge[cnt].next = head[a];
 31     edge[cnt].flow = c;
 32     edge[cnt].dis = d;
 33     head[a] = cnt;
 34 }
 35 
 36 int spfa(int st, int ed)
 37 {
 38     while(!Q.empty())
 39         Q.pop();
 40     mem(vis, 0), mem(flow, inf), mem(dis, inf), pre[ed] = -1;
 41     dis[st] = 0;
 42     vis[st] = 1;
 43     Q.push(st);
 44     while(!Q.empty())
 45     {
 46         int now = Q.front();
 47         Q.pop();
 48         vis[now] = 0;
 49         for(int i = head[now]; i != -1; i = edge[i].next)
 50         {
 51             int to = edge[i].to;
 52             if(edge[i].flow > 0 && dis[to] > dis[now] + edge[i].dis)
 53             {
 54                 dis[to] = dis[now] + edge[i].dis;
 55                 last[to] = i;
 56                 pre[to] = now;
 57                 flow[to] = min(flow[now], edge[i].flow);
 58                 if(!vis[to])
 59                 {
 60                     vis[to] = 1;
 61                     Q.push(to);
 62                 }
 63             }
 64         }
 65     }
 66     return pre[ed] != -1;
 67 }
 68 
 69 int min_cost, max_flow;
 70 void MCMF(int st, int ed)
 71 {
 72     min_cost = 0;
 73     max_flow = 0;
 74     while(spfa(st, ed))
 75     {
 76         int now = ed;
 77         min_cost += flow[ed]*dis[ed];
 78         max_flow += flow[ed];
 79         while(now != st)
 80         {
 81             edge[last[now]].flow -= flow[ed];
 82             edge[last[now] ^ 1].flow += flow[ed];
 83             now = pre[now];
 84         }
 85     }
 86 }
 87 
 88 int main()
 89 {
 90     scanf("%d%d%d", &n, &m, &k);
 91     mem(head, -1), cnt = -1, tot = 0;
 92     for(int i = 1; i <= m; i ++)
 93     {
 94         int a, b, c, d;
 95         scanf("%d%d%d%d", &a, &b, &c, &d);
 96         no[i].a = a, no[i].b = b, no[i].c = c, no[i].d = d;  //把输入的边记录下来
 97         add(a, b, c, 0);
 98         add(b, a, 0, 0);
 99     }
100     MCMF(1,n);
101     printf("%d ",max_flow);
102     for(int i = 1; i <= m; i ++) //在残留网络上加边 边的容量为 inf 费用为d 
103     {
104         add(no[i].a, no[i].b, inf, no[i].d);
105         add(no[i].b, no[i].a, 0, -no[i].d);
106     }
107     add(0, 1, k, 0);//加一个新的源点 0，容量为需要扩容的k，费用为 0。这样跑满流一定是k。
108     add(1, 0, 0, 0);
109     MCMF(0,n);
110     printf("%d
", min_cost);
111     return 0;
112 }

View Code