BZOJ 1834: [ZJOI2010]network 网络扩容

传送门

Description

Input

Output

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

Sample Input

Sample Output

13 19

刚开始傻逼傻逼地把原边都给清空了再重新建边。这样求出来的费用所能增加的K流量，不一定能使最大流变大K，因为走法肯定是不一样了。

所以必须在残量网络(跑完最大流后)的基础上加边。

#include 
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }return x * f;
}const int N = 5e3 + 10;
const int INF = 0x3f3f3f3f;
struct E { int v, ne, f, c; } e[N * 5];
int head[N], cnt, n, m, iter[N], level[N], k;
int path[N], dis[N], x[N * 5], y[N * 5], f[N * 5], c[N * 5];
bool inq[N];inline void add(int u, int v, int f, int c) {e[cnt].v = v; e[cnt].f = f; e[cnt].c = c; e[cnt].ne = head[u]; head[u] = cnt++;e[cnt].v = u; e[cnt].f = 0; e[cnt].c = -c; e[cnt].ne = head[v]; head[v] = cnt++;
}bool bfs(int s, int t) {for (int i = 0; i <= t; i++) level[i] = -1, iter[i] = head[i];queue<int> que;que.push(s);level[s] = 0;while (!que.empty()) {int u = que.front(); que.pop();for (int i = head[u]; ~i; i = e[i].ne) {int v = e[i].v, f = e[i].f;if (level[v] < 0 && f) {level[v] = level[u] + 1;que.push(v);}}}return level[t] != -1;
}bool spfa(int s, int t) {memset(dis, 0x3f, sizeof(dis));  memset(inq, 0, sizeof(inq));memset(path, -1, sizeof(path));queue<int> que;que.push(s);dis[s] = 0;inq[s] = 1;while (!que.empty()) {int u = que.front(); que.pop();inq[u] = false;for (int i = head[u]; ~i; i = e[i].ne) {int v = e[i].v;if (dis[v] > dis[u] + e[i].c && e[i].f) {dis[v] = dis[u] + e[i].c;path[v] = i;if (!inq[v]) {que.push(v);inq[v] = 1;}}}}return dis[t] != INF;
}int dfs(int u, int t, int f) {if (u == t || !f) return f;int flow = 0;for (int i = iter[u]; ~i; i = e[i].ne) {iter[u] = i;int v = e[i].v;if (level[v] == level[u] + 1 && e[i].f) {int w = dfs(v, t, min(f, e[i].f));if (!w) continue;e[i].f -= w, e[i^1].f += w;flow += w, f -= w;if (f <= 0) break; }}return flow;
}int mcf(int s, int t) {int ans = 0;while (spfa(s, t)) {int x = INF;for (int i = path[t]; ~i; i = path[e[i^1].v]) x = min(x, e[i].f);ans += x * dis[t];for (int i = path[t]; ~i; i = path[e[i^1].v]) e[i].f -= x, e[i^1].f += x;}return ans;
}int main() {memset(head, -1, sizeof(head));n = read(), m = read(), k = read();for (int i = 0; i < m; i++) {x[i] = read(), y[i] = read(), f[i] = read(), c[i] = read();add(x[i], y[i], f[i], 0);   }int ans = 0;for (; bfs(1, n); ans += dfs(1, n, INF));printf("%d ", ans);for (int i = 0; i < m; i++) add(x[i], y[i], INF, c[i]);add(0, 1, k, 0);printf("%d\n", mcf(0, n));return 0;
}

转载于:https://www.cnblogs.com/Mrzdtz220/p/10936841.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！