大连网站建设方案,宁波网站建设哪里好,兰州网络推广关键词优化,贵州省建设学校网站首页Description
给定一个 n n n \times n nn 的矩阵#xff0c;从左上角出发#xff0c;可以往右或者往下走#xff0c;每到达一个方格#xff0c;就取走上面的数#xff08;取过后格子上的数会清零#xff09;#xff0c;一共要走 k k k 次#xff0c;求取到的数之和…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;templateclass T
bool chmax(T a, const T b){if(a b){ a b; return true; }return false;
}templateclass 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::vectorEdge e;std::vectorstd::vectorint g;std::vectori64 h, dis;std::vectorint pre;bool dijkstra(int s, int t) {dis.assign(n, std::numeric_limitsi64::max());pre.assign(n, -1);std::priority_queuestd::pairi64, int, std::vectorstd::pairi64, int, std::greaterstd::pairi64, 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_limitsi64::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::pairint, 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_limitsint::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;
}
