結果
問題 | No.957 植林 |
ユーザー | risujiroh |
提出日時 | 2019-12-25 17:57:14 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 2,145 bytes |
コンパイル時間 | 1,895 ms |
コンパイル使用メモリ | 180,952 KB |
実行使用メモリ | 8,380 KB |
最終ジャッジ日時 | 2023-10-25 22:23:31 |
合計ジャッジ時間 | 18,242 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 21 ms
7,696 KB |
testcase_04 | AC | 20 ms
7,432 KB |
testcase_05 | AC | 19 ms
7,696 KB |
testcase_06 | AC | 22 ms
7,960 KB |
testcase_07 | AC | 21 ms
7,696 KB |
testcase_08 | AC | 15 ms
7,696 KB |
testcase_09 | AC | 14 ms
7,696 KB |
testcase_10 | AC | 16 ms
7,960 KB |
testcase_11 | AC | 15 ms
7,696 KB |
testcase_12 | AC | 15 ms
7,696 KB |
testcase_13 | AC | 12 ms
6,376 KB |
testcase_14 | AC | 15 ms
7,960 KB |
testcase_15 | AC | 13 ms
7,696 KB |
testcase_16 | AC | 12 ms
6,376 KB |
testcase_17 | AC | 13 ms
7,696 KB |
testcase_18 | AC | 403 ms
7,696 KB |
testcase_19 | AC | 423 ms
7,960 KB |
testcase_20 | AC | 446 ms
7,960 KB |
testcase_21 | AC | 453 ms
7,960 KB |
testcase_22 | AC | 492 ms
7,960 KB |
testcase_23 | AC | 510 ms
8,224 KB |
testcase_24 | AC | 546 ms
8,380 KB |
testcase_25 | AC | 587 ms
8,224 KB |
testcase_26 | AC | 582 ms
8,224 KB |
testcase_27 | AC | 586 ms
8,224 KB |
testcase_28 | AC | 578 ms
8,224 KB |
testcase_29 | AC | 587 ms
8,224 KB |
testcase_30 | AC | 578 ms
8,224 KB |
testcase_31 | AC | 401 ms
7,696 KB |
testcase_32 | AC | 413 ms
7,960 KB |
testcase_33 | AC | 455 ms
7,960 KB |
testcase_34 | AC | 464 ms
7,960 KB |
testcase_35 | AC | 493 ms
7,960 KB |
testcase_36 | AC | 525 ms
8,224 KB |
testcase_37 | AC | 550 ms
8,380 KB |
testcase_38 | AC | 577 ms
8,224 KB |
testcase_39 | AC | 572 ms
8,224 KB |
testcase_40 | AC | 589 ms
8,224 KB |
testcase_41 | AC | 7 ms
4,348 KB |
testcase_42 | AC | 7 ms
4,348 KB |
testcase_43 | AC | 17 ms
8,224 KB |
testcase_44 | AC | 19 ms
8,224 KB |
testcase_45 | AC | 2 ms
4,348 KB |
testcase_46 | AC | 1 ms
4,348 KB |
testcase_47 | AC | 2 ms
4,348 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<class T> struct Dinic { struct Edge { int to, rev; T cap; }; const T inf = numeric_limits<T>::max(); const int n; vector< vector<Edge> > g; vector<int> dist, i; Dinic(int _n) : n(_n), g(n), dist(n), i(n) {} void add_edge(int from, int to, T cap) { assert(from != to); assert(cap >= 0); if (!cap) return; g[from].emplace_back(Edge{to, (int)g[to].size(), cap}); g[to].emplace_back(Edge{from, (int)g[from].size() - 1, 0}); } void bfs(int s) { fill(begin(dist), end(dist), -1); queue<int> que; dist[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (const auto& e : g[v]) { if (dist[e.to] != -1 or !e.cap) continue; dist[e.to] = dist[v] + 1; que.push(e.to); } } } T dfs(int v, int s, T f) { if (v == s) return f; for (; i[v] < (int)g[v].size(); ++i[v]) { Edge& e = g[v][i[v]]; if (dist[e.to] >= dist[v] or !g[e.to][e.rev].cap) continue; T d = dfs(e.to, s, min(f, g[e.to][e.rev].cap)); if (d > 0) { g[e.to][e.rev].cap -= d; e.cap += d; return d; } } return 0; } T max_flow(int s, int t) { assert(s != t); T res = 0; while (true) { bfs(s); if (dist[t] == -1) return res; fill(begin(i), end(i), 0); while (true) { T f = dfs(t, s, inf); if (!f) break; res += f; } } } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; int s = h + w, t = s + 1; Dinic<long long> g(t + 1); long long res = 0; vector<long long> sc(w); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { int c; cin >> c; g.add_edge(i, h + j, c); sc[j] += c; } } for (int i = 0; i < h; ++i) { int a; cin >> a; res += a; g.add_edge(s, i, a); } for (int j = 0; j < w; ++j) { int b; cin >> b; res += b; g.add_edge(s, h + j, b); g.add_edge(h + j, t, sc[j]); } res -= g.max_flow(s, t); cout << res << '\n'; }