P2045 方格取数加强版
Description
给定一个 n × n n \times n n×n 的矩阵,从左上角出发,可以往右或者往下走,每到达一个方格,就取走上面的数(取过后格子上的数会清零),一共要走 k k k 次,求取到的数之和最大为多少?
Analysis
网络流题,考虑如何建图。
首先,建立超级源点和超级汇点,源点向 ( 1 , 1 ) (1,1) (1,1) 连边, ( n , n ) (n,n) (n,n) 向汇点连边,容量均为 k k k,费用均为 0 0 0,表示一共要走 k k k 次。
将方格中的每个点拆成入点和出点,中间连两条边,一条容量为 1 1 1,费用为 k k k,另一条容量为 k − 1 k-1 k−1,费用为 0 0 0(因为每个格子的数只可以取一次)。
每个格子的出点向其右和其下格子的入点分别连一条边,容量为 ∞ \infty ∞,费用为 0 0 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;
}