P2045 方格取数加强版

Description

给定一个 $n\times n$ 的矩阵，从左上角出发，可以往右或者往下走，每到达一个方格，就取走上面的数（取过后格子上的数会清零），一共要走 $k$ 次，求取到的数之和最大为多少？

Analysis

网络流题，考虑如何建图。

首先，建立超级源点和超级汇点，源点向 $(1,1)$ 连边，$(n,n)$ 向汇点连边，容量均为 $k$，费用均为 $0$，表示一共要走 $k$ 次。

将方格中的每个点拆成入点和出点，中间连两条边，一条容量为 $1$，费用为 $k$，另一条容量为 $k-1$，费用为 $0$（因为每个格子的数只可以取一次）。

每个格子的出点向其右和其下格子的入点分别连一条边，容量为 $\infty$，费用为 $0$（仅表示一种连通的关系）。

在建成的图上，跑最大费用最大流即可。

Code

MCF 的板子是贴 jiangly 的。

// Problem: P2045 方格取数加强版
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2045
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}struct MCFGraph {struct Edge {int v, c, f;Edge(int v, int c, int f) : v(v), c(c), f(f) {}};const int n;std::vector<Edge> e;std::vector<std::vector<int>> g;std::vector<i64> h, dis;std::vector<int> pre;bool dijkstra(int s, int t) {dis.assign(n, std::numeric_limits<i64>::max());pre.assign(n, -1);std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> que;dis[s] = 0;que.emplace(0, s);while (!que.empty()) {i64 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 f = e[i].f;if (c > 0 && dis[v] > d + h[u] - h[v] + f) {dis[v] = d + h[u] - h[v] + f;pre[v] = i;que.emplace(dis[v], v);}}}return dis[t] != std::numeric_limits<i64>::max();}MCFGraph(int n) : n(n), g(n) {}void addEdge(int u, int v, int c, int f) {g[u].push_back(e.size());e.emplace_back(v, c, f);g[v].push_back(e.size());e.emplace_back(u, 0, -f);}std::pair<int, i64> flow(int s, int t) {int flow = 0;i64 cost = 0;h.assign(n, 0);while (dijkstra(s, t)) {for (int i = 0; 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 += i64(aug) * h[t];}return std::make_pair(flow, cost);}
};const int INF = 1e9;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;auto in = [&](int x, int y) { return x * n + y; };auto out = [&](int x, int y) { return in(x, y) + n * n; };MCFGraph G(n * n * 2 + 2);int S = n * n * 2, T = S + 1;G.addEdge(S, in(0, 0), k, 0);G.addEdge(out(n - 1, n - 1), T, k, 0);for (int i = 0; i < n; i++)for (int j = 0, x; j < n; j++) {cin >> x;G.addEdge(in(i, j), out(i, j), 1, -x);G.addEdge(in(i, j), out(i, j), k - 1, 0);if (i < n - 1) G.addEdge(out(i, j), in(i + 1, j), INF, 0);if (j < n - 1) G.addEdge(out(i, j), in(i, j + 1), INF, 0);}auto [_, cost] = G.flow(S, T);cout << -cost << endl;return 0;
}