結果
| 問題 |
No.957 植林
|
| コンテスト | |
| ユーザー |
 KoD
|
| 提出日時 | 2020-07-17 17:06:55 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 233 ms / 2,000 ms |
| コード長 | 6,488 bytes |
| コンパイル時間 | 4,119 ms |
| コンパイル使用メモリ | 133,708 KB |
| 最終ジャッジ日時 | 2025-01-11 21:48:48 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
ソースコード
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <queue>
#include <list>
template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) { lhs = rhs; return true; }
return false;
}
template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) { lhs = rhs; return true; }
return false;
}
struct range {
using itr = int64_t;
struct iterator {
itr i;
constexpr iterator(itr i_) noexcept : i(i_) { }
constexpr void operator ++ () noexcept { ++i; }
constexpr itr operator * () const noexcept { return i; }
constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
};
const iterator l, r;
constexpr range(itr l_, itr r_) noexcept : l(l_), r(std::max(l_, r_)) { }
constexpr iterator begin() const noexcept { return l; }
constexpr iterator end() const noexcept { return r; }
};
struct revrange {
using itr = int64_t;
struct iterator {
itr i;
constexpr iterator(itr i_) noexcept : i(i_) { }
constexpr void operator ++ () noexcept { --i; }
constexpr itr operator * () const noexcept { return i; }
constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
};
const iterator l, r;
constexpr revrange(itr l_, itr r_) noexcept : l(l_ - 1), r(std::max(l_, r_) - 1) { }
constexpr iterator begin() const noexcept { return r; }
constexpr iterator end() const noexcept { return l; }
};
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
struct edge_t {
i32 to;
i64 cap;
i32 rev;
};
int main() {
i32 H, W;
std::cin >> H >> W;
i32 V = H + W + 2;
i32 source = H + W, sink = H + W + 1;
std::vector<std::vector<edge_t>> graph(V);
auto add_edge = [&](i32 u, i32 v, i64 c) {
graph[u].push_back(edge_t{ v, c, (i32) graph[v].size() });
graph[v].push_back(edge_t{ u, 0, (i32) graph[u].size() - 1 });
};
std::vector<i64> accum(H);
for (auto i: range(0, H)) {
for (auto j: range(0, W)) {
i32 g;
std::cin >> g;
accum[i] += g;
add_edge(i, H + j, g);
}
}
i64 sum = 0;
for (auto i: range(0, H)) {
i64 r;
std::cin >> r;
i64 min = std::min(accum[i], r);
sum += r - min;
add_edge(source, i, accum[i] - min);
}
for (auto i: range(0, W)) {
i64 r;
std::cin >> r;
sum += r;
add_edge(H + i, sink, r);
}
i32 min_gap, max_active;
std::vector<std::list<i32>> active(V), inactive(V);
std::vector<i32> height(V), seen(V), count(V);
std::vector<i64> excess(V);
std::vector<typename std::list<i32>::iterator> iter(V);
i32 counter = 0;
auto push = [&](auto u, edge_t &e) { // Push flow from the node.
i64 flow = std::min(e.cap, excess[u]);
e.cap -= flow;
graph[e.to][e.rev].cap += flow;
excess[u] -= flow;
excess[e.to] += flow;
};
auto relabel = [&](auto u) { // Relabel the node so that there will be an admissible edge.
++counter;
i32 min = V + 1;
for (auto &e: graph[u]) {
if (e.cap > 0) {
chmin(min, height[e.to] + 1);
}
}
height[u] = min;
};
auto reverse_bfs = [&] { // Compute exact heights.
std::fill(height.begin(), height.end(), V + 1);
height[sink] = 0;
std::queue<i32> que;
que.push(sink);
while (!que.empty()) {
i32 u = que.front();
que.pop();
for (auto e: graph[u]) {
if (graph[e.to][e.rev].cap > 0) {
if (chmin(height[e.to], height[u] + 1)) {
que.push(e.to);
}
}
}
}
};
auto set_active = [&] { // Count nodes with each height and set active nodes.
min_gap = V;
max_active = 0;
for (auto h: range(0, V)) {
active[h].clear();
inactive[h].clear();
count[h] = 0;
}
for (auto u: range(0, V)) {
if (height[u] < V) {
count[height[u]]++;
if (excess[u] > 0) {
iter[u] = active[height[u]].insert(active[height[u]].end(), u);
chmax(max_active, height[u]);
}
else {
iter[u] = inactive[height[u]].insert(inactive[height[u]].end(), u);
}
}
}
for (auto h: range(0, V)) {
if (count[h] == 0) {
min_gap = h;
break;
}
}
};
auto discharge = [&](auto u) { // Apply push/relabel until the node becomes inactive.
while (true) {
auto &e = graph[u][seen[u]];
if (e.cap > 0 && height[u] == height[e.to] + 1) {
{
if (excess[e.to] == 0) {
inactive[height[e.to]].erase(iter[e.to]);
iter[e.to] = active[height[e.to]].insert(active[height[e.to]].end(), e.to);
chmax(max_active, height[e.to]);
}
}
push(u, e);
if (excess[u] == 0) {
iter[u] = inactive[height[u]].insert(inactive[height[u]].end(), u);
break;
}
}
seen[u]++;
if (seen[u] == graph[u].size()) {
seen[u] = 0;
count[height[u]]--;
if (count[height[u]] == 0) {
for (auto i: range(height[u], min_gap)) {
for (auto v: active[i]) {
height[v] = V + 1;
}
for (auto v: inactive[i]) {
height[v] = V + 1;
}
active[i].clear();
inactive[i].clear();
}
height[u] = V + 1;
break;
}
relabel(u);
if (height[u] > min_gap) {
height[u] = V + 1;
break;
}
if (height[u] == min_gap) {
min_gap++;
}
count[height[u]]++;
}
}
};
{ // Preprocess
reverse_bfs();
if (height[source] == V + 1) {
std::cout << sum << '\n';
return 0;
}
for (auto &e: graph[source]) {
excess[source] += e.cap;
push(source, e);
}
height[source] = V;
set_active();
}
{ // Main Process
while (max_active > 0) {
if (active[max_active].empty()) {
--max_active;
continue;
}
auto itr = active[max_active].begin();
active[max_active].erase(itr);
discharge(*itr);
if (counter >= V) {
counter -= V;
reverse_bfs();
set_active();
}
chmin(max_active, min_gap - 1);
}
}
std::cout << sum - excess[sink] << '\n';
return 0;
}