02/22
15:22
Description
给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1到N的最大流; 2、 将1到N的最大流增加K所需的最小扩容费用。
Input
输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。
Output
输出文件一行包含两个整数,分别表示问题1和问题2的答案。
Sample Input
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 19
30%的数据中,N<=100
100%的数据中,N<=1000,M<=5000,K<=10
HINT
Source
Day1
Solution
对于第一问,直接跑最大流算法即可。
对于第二问,在残量网络上建边,每一条边的流量为inf,费用为w,超级源跟1建边,流量为k,费用为0, 再跑最小费用最大流就好了。
(为什么可以这样? 在残量网络上,那些不需要扩容的边花费为0,所以必定会选中,不需要花费额外的花费)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int SZ = 1e5 + 10; const int INF = 1e9; struct Edge { int f, t, v, c; }es[SZ]; struct data { int a, b; }; int first[SZ], nxt[SZ], tot = 1, s, t; struct MCMF { int dis[SZ], from[SZ]; bool vis[SZ]; queue<int> Q; bool spfa() { for(int i = 1; i <= t; i++) dis[i] = INF; Q.push(s); vis[s] = 1; dis[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(es[i].v && dis[v] > dis[u] + es[i].c) { dis[v] = dis[u] + es[i].c; from[v] = i; if(!vis[v]) { vis[v] = 1; Q.push(v); } } } } return dis[t] != INF; } data solve() { int ans1 = 0, ans2 = 0; while(spfa()) { int i = from[t], num = INF; while(i) { num = min(num, es[i].f); i = from[es[i].f]; } ans1 += num; i = from[t]; while(i) { es[i].v -= num; es[i ^ 1].v += num; ans2 += num * es[i].c; i = from[es[i].f]; } } return (data){ans1, ans2}; } }mcmf; int u[SZ], v[SZ], w[SZ]; void insert(int f, int t, int v, int c) { es[++tot] = (Edge){f, t, v, c}; nxt[tot] = first[f]; first[f] = tot; es[++tot] = (Edge){t, f, 0, -c}; nxt[tot] = first[t]; first[t] = tot; } int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); s = 1, t = n; int d; for(int i = 1; i <= m; i++) { scanf("%d%d%d%d", &u[i], &v[i], &d, &w[i]); insert(u[i], v[i], d, 0); } printf("%d ", mcmf.solve().a); for(int i = 1; i <= m; i++) insert(u[i], v[i], INF, w[i]); s = n + 1; insert(s, 1, k, 0); printf("%d", mcmf.solve().b); return 0; } |