【最小费用最大流】JZOJ

【最小费用最大流】JZOJ_4802 探险计划

本文主要是介绍【最小费用最大流】JZOJ_4802 探险计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个梯形，每个点上有一个危险值，从底部出发，每次能走到左上或者右上的点。

任务一：找出 $m$ 条完全不相交的至底至顶的路径
任务二：找出 $m$ 条仅在数字处相交的路径(可以重复经过点)

对于两个任务，求出最小的危险值总和。

思路

最小费用最大流。

将每个点拆点，对于任务一，给一个限制，任务二则无限制。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>int n, m, tot, S, E, SS, sum, ans;
int a[81][161], ver[58001], next[58001], head[20004], flow[58001], cost[58001], d[20004], v[20004], pre[20004], p[81][161];inline void add(int u, int v, int f, int c) {ver[++tot] = v;next[tot] = head[u];flow[tot] = f;cost[tot] = c;head[u] = tot;ver[++tot] = u;next[tot] = head[v];flow[tot] = 0;cost[tot] = -c;head[v] = tot;
}inline int spfa() {std::queue<int> q;memset(d, 127 / 3, sizeof(d));memset(v, 0, sizeof(v));memset(pre, 0, sizeof(pre));d[SS] = 0;v[SS] = 1;q.push(SS);while (q.size()) {int u = q.front();q.pop();v[u] = 0;for (register int i = head[u]; i; i = next[i]) {if (!flow[i]) continue;if (d[ver[i]] > d[u] + cost[i]) {d[ver[i]] = d[u] + cost[i];pre[ver[i]] = i;if (!v[ver[i]]) {q.push(ver[i]);v[ver[i]] = 1;}}}}return d[E] < 707406378;
}inline void addflow() {int i = E, mn = 2147483647;while (pre[i]) {mn = std::min(mn, flow[pre[i]]);i = ver[pre[i] ^ 1];}ans += mn * d[E];i = E;while (pre[i]) {flow[pre[i]] -= mn;flow[pre[i] ^ 1] += mn;i = ver[pre[i] ^ 1];}
}int main() {scanf("%d %d", &n, &m);int tj = 0, sum = (m + m + n - 1) * n / 2;tot = 1;for (register int i = 1; i <= n; i++)for (register int j = 1; j < m + i; j++) {scanf("%d", &a[i][j]);p[i][j] = ++tj;add(p[i][j], p[i][j] + sum, 1, 0);}S = 0;E = 2 * sum + 1;SS = 2 * sum + 2;add(SS, S, m, 0);for (register int i = 1; i < m + n; i++)add(S, p[n][i], m, a[n][i]);for (register int i = 1; i <= m; i++)add(p[1][i] + sum, E, m, 0);for (register int i = 2; i <= n; i++) {for (register int j = 1; j < m + i; j++) {if (j < m + i - 1) add(p[i][j] + sum, p[i - 1][j], 1, a[i - 1][j]);if (j > 1) add(p[i][j] + sum, p[i - 1][j - 1], 1, a[i - 1][j - 1]);}}while (spfa())addflow();printf("%d\n", ans);tot = 1;ans = 0;memset(head, 0, sizeof(head));add(SS, S, m, 0);for (register int i = 1; i < m + n; i++)add(S, p[n][i], m, a[n][i]);for (register int i = 1; i <= m; i++)add(p[1][i] + sum, E, m, 0);for (register int i = 1; i <= n; i++) {for (register int j = 1; j < m + i; j++) {add(p[i][j], p[i][j] + sum, m, 0);if (i > 1 && j < m + i - 1) add(p[i][j] + sum, p[i - 1][j], 1, a[i - 1][j]);if (i > 1 && j > 1) add(p[i][j] + sum, p[i - 1][j - 1], 1, a[i - 1][j - 1]);}}while (spfa())addflow();printf("%d", ans);	
}