题目链接：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，会优先用）
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int MAXM = ;
const int MAXN = ;
const int inf = 0x3f3f3f3f; int n, m, k; //n个点 m条有向边, 扩容k
queue<int> Q;
int dep[MAXN], last[MAXN], pre[MAXN], dis[MAXN], flow[MAXN], vis[MAXN]; struct Node
{
int a, b, c, d;
}no[MAXM];
int tot; struct Edge
{
int to, next, flow, dis;
}edge[ * MAXN];
int head[MAXN], cnt; void add(int a, int b, int c, int d)
{
edge[++ cnt].to = b;
edge[cnt].next = head[a];
edge[cnt].flow = c;
edge[cnt].dis = d;
head[a] = cnt;
} int spfa(int st, int ed)
{
while(!Q.empty())
Q.pop();
mem(vis, ), mem(flow, inf), mem(dis, inf), pre[ed] = -;
dis[st] = ;
vis[st] = ;
Q.push(st);
while(!Q.empty())
{
int now = Q.front();
Q.pop();
vis[now] = ;
for(int i = head[now]; i != -; i = edge[i].next)
{
int to = edge[i].to;
if(edge[i].flow > && dis[to] > dis[now] + edge[i].dis)
{
dis[to] = dis[now] + edge[i].dis;
last[to] = i;
pre[to] = now;
flow[to] = min(flow[now], edge[i].flow);
if(!vis[to])
{
vis[to] = ;
Q.push(to);
}
}
}
}
return pre[ed] != -;
} int min_cost, max_flow;
void MCMF(int st, int ed)
{
min_cost = ;
max_flow = ;
while(spfa(st, ed))
{
int now = ed;
min_cost += flow[ed]*dis[ed];
max_flow += flow[ed];
while(now != st)
{
edge[last[now]].flow -= flow[ed];
edge[last[now] ^ ].flow += flow[ed];
now = pre[now];
}
}
} int main()
{
scanf("%d%d%d", &n, &m, &k);
mem(head, -), cnt = -, tot = ;
for(int i = ; i <= m; i ++)
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
no[i].a = a, no[i].b = b, no[i].c = c, no[i].d = d; //把输入的边记录下来
add(a, b, c, );
add(b, a, , );
}
MCMF(,n);
printf("%d ",max_flow);
for(int i = ; i <= m; i ++) //在残留网络上加边 边的容量为 inf 费用为d
{
add(no[i].a, no[i].b, inf, no[i].d);
add(no[i].b, no[i].a, , -no[i].d);
}
add(, , k, );//加一个新的源点 0，容量为需要扩容的k，费用为 0。这样跑满流一定是k。
add(, , , );
MCMF(,n);
printf("%d\n", min_cost);
return ;
}