【网络流】网络扩容 OI

【问题描述】给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。【输入格式】network.in 输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。【输出格式】network.out 输出文件一行包含两个整数，分别表示问题1和问题2的答案。【输入样例】 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 【输出样例】 13 19 【数据规模】 30%的数据中，N<=100 100%的数据中，N<=1000，M<=5000，K<=10

这是一道最大流加最小费用流的问题。

最大流就不再多说了。

求出了最大流之后有个残量网络，将这些边的费用设为0（原图中剩余的流量免费），重新加入一些边（前提是原图中有这些边，于是），流量为k，费用为扩容费用，再加一个超级源，连一条容量为k，费用为0的边（限制流量最大为k），最后求一次最小费用流即可。
Accode：

#include #include #include #include #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b))const char fi[] = "network.in"; const char fo[] = "network.out"; const int maxN = 1010; const int SIZE = 0x3ff; const int MAX = 0x3f3f3f3f; const int MIN = ~MAX; struct Edge { int u, v, f, c; Edge *next, *back; }; Edge *edge[maxN]; Edge *pre[maxN]; bool mp[maxN][maxN]; int w[maxN][maxN]; int d[maxN]; int cnt[maxN]; int q[SIZE + 1]; int n, m, K, S = 1, T, f, r; void init_file() { freopen(fi, "r", stdin); freopen(fo, "w", stdout); return; }inline int getint() { int res = 0; char tmp; while (!isdigit(tmp = getchar())); do res = (res << 3) + (res << 1) + tmp - '0'; while (isdigit(tmp = getchar())); return res; }inline void insert(int u, int v, int f, int c) { Edge *p = new Edge; p -> u = u; p -> v = v; p -> f = f; p -> c = c; p -> next = edge[u]; edge[u] = p; p = new Edge; p -> u = v; p -> v = u; p -> f = 0; p -> c = -c; p -> next = edge[v]; edge[v] = p; edge[u] -> back = edge[v]; edge[v] -> back = edge[u]; return; }void readdata() { T = n = getint(); m = getint(); K = getint(); for (; m; --m) { int u = getint(), v = getint(), f = getint(), c = getint(); mp[u][v] = 1; //先用mp数组记录一下原图中有哪些边。 w[u][v] = w[u][v] ? min(w[u][v], c) : c; //记录扩容费用。 insert(u, v, f, 0); } return; }int Sap(int u, int Lim) { if (u == T) return Lim; int tmp = 0; for (Edge *p = edge[u]; p; p = p -> next) if (p -> f > 0 && d[u] == d[p -> v] + 1) { int k = Sap(p -> v, min(p -> f, Lim - tmp)); p -> f -= k; p -> back -> f += k; if ((tmp += k) == Lim) return tmp; } if (d[S] >= n) return tmp; if ((--cnt[d[u]]) == 0) d[S] = n; ++cnt[++d[u]]; return tmp; }int Spfa() { memset(pre, 0, sizeof pre); memset(d, 0x3f, sizeof d); memset(cnt, 0, sizeof cnt); f = r = 0; d[S] = 0; ++cnt[q[r++] = S]; r &= SIZE; while (f != r) { int u = q[f++]; f &= SIZE; --cnt[u]; for (Edge *p = edge[u]; p; p = p -> next) if (p -> f > 0) { int v = p -> v; int c = p -> c; if (d[u] + c < d[v]) { d[v] = d[u] + c; pre[v] = p; if (!cnt[v]) { ++cnt[q[r++] = v]; r &= SIZE; } } } } return pre[T] != NULL; }int min_fee() { int ans = 0; while (Spfa()) { int max_flow = MAX; for (Edge *p = pre[T]; p; p = pre[p -> u]) max_flow = min(max_flow, p -> f); for (Edge *p = pre[T]; p; p = pre[p -> u]) { p -> f -= max_flow; p -> back -> f += max_flow; } ans += d[T] * max_flow; } return ans; }void work() { int ans = 0; cnt[0] = n; while (d[S] < n) ans += Sap(S, MAX); for (int u = 1; u < n + 1; ++u) for (int v = 1; v < n + 1; ++v) if (mp[u][v]) insert(u, v, MAX, w[u][v]); insert(S = 0, 1, K, 0); printf("%d %d\n", ans, min_fee()); return; }int main() { init_file(); readdata(); work(); return 0; }#undef min #undef max

再贴一个求费用流时没有退流的骗分程序，能过90分。

#include #include #include #include #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b))const char fi[] = "network.in"; const char fo[] = "network.out"; const int maxN = 1010; const int SIZE = 0x3ff; const int MAX = 0x3f3f3f3f; const int MIN = ~MAX; struct Edge { int u, v, f, c; Edge *next, *back; }; Edge *edge[maxN]; int d[maxN]; int cnt[maxN]; int q[SIZE + 1]; int n, m, K, S = 1, T, f, r; void init_file() { freopen(fi, "r", stdin); freopen(fo, "w", stdout); return; }inline int getint() { int res = 0; char tmp; while (!isdigit(tmp = getchar())); do res = (res << 3) + (res << 1) + tmp - '0'; while (isdigit(tmp = getchar())); return res; }inline void insert(int u, int v, int f, int c) { for (Edge *p = edge[u]; p; p = p -> next) if (p -> v == v) { p -> f += f; p -> c = min(p -> c, c); return; } Edge *p = new Edge; p -> u = u; p -> v = v; p -> f = f; p -> c = c; p -> next = edge[u]; edge[u] = p; p = new Edge; p -> u = v; p -> v = u; p -> f = 0; p -> c = MAX; p -> next = edge[v]; edge[v] = p; edge[u] -> back = edge[v]; edge[v] -> back = edge[u]; return; }void readdata() { T = n = getint(); m = getint(); K = getint(); for (; m; --m) { int u = getint(), v = getint(), f = getint(), c = getint(); insert(u, v, f, c); } return; }int Sap(int u, int Lim) { if (u == T) return Lim; int tmp = 0; for (Edge *p = edge[u]; p; p = p -> next) if (p -> f > 0 && d[u] == d[p -> v] + 1) { int k = Sap(p -> v, min(p -> f, Lim - tmp)); p -> f -= k; p -> back -> f += k; if ((tmp += k) == Lim) return tmp; } if (d[S] >= n) return tmp; if ((--cnt[d[u]]) == 0) d[S] = n; ++cnt[++d[u]]; return tmp; }int Spfa() { memset(d, 0x3f, sizeof d); memset(cnt, 0, sizeof cnt); d[S] = 0; ++cnt[q[r++] = S]; r &= SIZE; while (f != r) { int u = q[f++]; f &= SIZE; --cnt[u]; for (Edge *p = edge[u]; p; p = p -> next) if (p -> c < MAX) { int v = p -> v; int c = (p -> c) * max(0, K - p -> f); if (d[u] + c < d[v]) { d[v] = d[u] + c; if (!cnt[v]) { ++cnt[q[r++] = v]; r &= SIZE; } } } } return d[T]; }void work() { int ans = 0; cnt[0] = n; while (d[S] < n) ans += Sap(S, MAX); printf("%d %d\n", ans, K ? Spfa() : 0); return; }int main() { init_file(); readdata(); work(); return 0; }#undef min #undef max

【【网络流】网络扩容】