网络流 24 题」数字梯形
思路
对于规则 1 1 1，要求的是点不相交且边不相交，我们可以把边的容量设置成 1 1 1，把点拆分成入点和出点，将其内部的容量设置成 1 1 1，这样就可以限制点的流量。
把相应的点之间的边的费用设置成点权的负数，跑最小费用最大流即可
对于规则 2 2 2，允许在数字节点处相交，我们就不用拆点来限制点内流量了，但是点和点之间的边的容量还是为 1 1 1，这样子就允许一个点多次使用，但边只能使用一次
对于规则 3 3 3，我们只需要将所有边权的容量设置为 ∞ \infty ∞ 即可
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;struct MCF {struct Edge {int v, c, w; //边终点、容量、费用Edge(int v, int c, int w) : v(v), c(c), w(w) {}};const int n;std::vector<Edge> e;std::vector<std::vector<int>> g;std::vector<ll> h, dis;std::vector<int> pre;bool dijkstra(int s, int t) {dis.assign(n + 1, std::numeric_limits<ll>::max());pre.assign(n + 1, -1);std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<std::pair<ll, int>>> que;dis[s] = 0;que.emplace(0, s);while (!que.empty()) {ll d = que.top().first;int u = que.top().second;que.pop();if (dis[u] < d) continue;for (int i : g[u]) {int v = e[i].v;int c = e[i].c;int w = e[i].w;if (c > 0 && dis[v] > d + h[u] - h[v] + w) {dis[v] = d + h[u] - h[v] + w;pre[v] = i;que.emplace(dis[v], v);}}}return dis[t] != std::numeric_limits<ll>::max();}MCF(int n) : n(n), g(n + 1) {}void addEdge(int u, int v, int c, int w) {g[u].push_back(e.size());e.emplace_back(v, c, w);g[v].push_back(e.size());e.emplace_back(u, 0, -w);}std::pair<int, ll> flow(int s, int t) {int flow = 0;ll cost = 0;h.assign(n + 1, 0);while (dijkstra(s, t)) {for (int i = 1; i <= n; ++i) h[i] += dis[i];int aug = std::numeric_limits<int>::max();for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);for (int i = t; i != s; i = e[pre[i] ^ 1].v) {e[pre[i]].c -= aug;e[pre[i] ^ 1].c += aug;}flow += aug;cost += ll(aug) * h[t];}return std::make_pair(flow, cost);}
};const int N = 100;int a[N][N];
int id[N][N];
int tot;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int m, n;std::cin >> m >> n; fore(i, 1, n + 1)fore(j, 1, i + m){std::cin >> a[i][j];a[i][j] *= -1;id[i][j] = ++tot;}MCF mcf(2 * tot + 2);int S = 2 * tot + 1, T = S + 1;fore(j, 1, m + 1) mcf.addEdge(S, 2 * id[1][j] - 1, INF, 0);fore(i, 1, n)fore(j, 1, i + m){int in = 2 * id[i][j] - 1, out = in + 1;mcf.addEdge(in, out, 1, a[i][j]);mcf.addEdge(out, 2 * id[i + 1][j] - 1, 1, 0);mcf.addEdge(out, 2 * id[i + 1][j + 1] - 1, 1, 0);}fore(j, 1, n + m){int in = id[n][j] * 2 - 1, out = id[n][j] * 2;mcf.addEdge(in, out, 1, a[n][j]);mcf.addEdge(out, T, 1, 0);}std::cout << -mcf.flow(S, T).se << endl;MCF mcf2(tot + 2);S = tot + 1, T = S + 1;fore(j, 1, m + 1) mcf2.addEdge(S, id[1][j], 1, 0);fore(i, 1, n)fore(j, 1, i + m){mcf2.addEdge(id[i][j], id[i + 1][j], 1, a[i][j]);mcf2.addEdge(id[i][j], id[i + 1][j + 1], 1, a[i][j]);}fore(j, 1, n + m){mcf2.addEdge(id[n][j], T, INF, a[n][j]);}std::cout << -mcf2.flow(S, T).se << endl;S = 2 * tot + 1, T = S + 1;MCF mcf3(2 * tot + 2);fore(j, 1, m + 1) mcf3.addEdge(S, 2 * id[1][j] - 1, 1, 0);fore(i, 1, n)fore(j, 1, i + m){int in = 2 * id[i][j] - 1, out = in + 1;mcf3.addEdge(in, out, INF, a[i][j]);mcf3.addEdge(out, 2 * id[i + 1][j] - 1, INF, 0);mcf3.addEdge(out, 2 * id[i + 1][j + 1] - 1, INF, 0);}fore(j, 1, n + m){int in = id[n][j] * 2 - 1, out = id[n][j] * 2;mcf3.addEdge(in, out, INF, a[n][j]);mcf3.addEdge(out, T, INF, 0);}std::cout << -mcf3.flow(S, T).se << endl;return 0;
}
