結果
問題 | No.957 植林 |
ユーザー | risujiroh |
提出日時 | 2019-12-19 23:00:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,168 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 175,528 KB |
実行使用メモリ | 26,524 KB |
最終ジャッジ日時 | 2023-09-21 07:37:03 |
合計ジャッジ時間 | 15,487 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1,013 ms
21,772 KB |
testcase_04 | AC | 857 ms
20,180 KB |
testcase_05 | AC | 1,117 ms
22,584 KB |
testcase_06 | AC | 563 ms
24,228 KB |
testcase_07 | AC | 1,260 ms
21,244 KB |
testcase_08 | AC | 492 ms
22,052 KB |
testcase_09 | AC | 506 ms
22,076 KB |
testcase_10 | AC | 654 ms
23,056 KB |
testcase_11 | AC | 569 ms
22,036 KB |
testcase_12 | AC | 541 ms
22,008 KB |
testcase_13 | AC | 290 ms
18,924 KB |
testcase_14 | AC | 494 ms
24,060 KB |
testcase_15 | AC | 465 ms
21,820 KB |
testcase_16 | AC | 265 ms
19,220 KB |
testcase_17 | AC | 321 ms
21,080 KB |
testcase_18 | TLE | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; // https://kopricky.github.io/code/NetworkFlow/dinic.html template<typename T> class Dinic { private: static_assert(std::is_integral<T>::value, "Integral required."); struct edge{ int to; T cap; int rev; }; const int V; vector<int> level, iter, que; static unsigned long long floor2(unsigned long long v){ v = v | (v >> 1), v = v | (v >> 2); v = v | (v >> 4), v = v | (v >> 8); v = v | (v >> 16), v = v | (v >> 32); return v - (v >> 1); } void bfs(const int s, const T base) { fill(level.begin(), level.end(), -1); level[s] = 0; int qh = 0, qt = 0; for(que[qt++] = s; qh < qt;){ int v = que[qh++]; for(edge& e : G[v]){ if(level[e.to] < 0 && e.cap >= base){ level[e.to] = level[v] + 1; que[qt++] = e.to; } } } } T dfs(const int v, const int t, const T base, const T f) { if(v == t) return f; T sum = 0; for(int& i = iter[v]; i < (int)G[v].size(); i++){ edge& e = G[v][i]; if(e.cap >= base && level[v] < level[e.to]){ T d = dfs(e.to, t, base, min(f - sum, e.cap)); if(d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; sum += d; if(f - sum < base) break; } } } return sum; } public: vector<vector<edge> > G; Dinic(const int node_size) : V(node_size), level(V), iter(V), que(V), G(V){} //辺を張る void add_edge(const int from, const int to, const T cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, (T)0, (int)G[from].size()-1}); } //最大流を計算(max_cap は辺の容量の上限) T solve(const int s, const int t, const T max_cap){ T flow = 0; for(T base = floor2(max_cap); base >= 1;){ bfs(s, base); if(level[t] < 0){ base >>= 1; continue; } fill(iter.begin(), iter.end(), 0); flow += dfs(s, t, base, numeric_limits<T>::max()); } return flow; } }; constexpr long long inf = 1e18; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; int s = h * w + h + w, t = s + 1; Dinic<long long> g(t + 1); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { int a; cin >> a; g.add_edge(i * w + j, t, a); } } long long res = 0; for (int i = 0; i < h; ++i) { int a; cin >> a; res += a; g.add_edge(s, h * w + i, a); for (int j = 0; j < w; ++j) { g.add_edge(h * w + i, i * w + j, inf); } } for (int j = 0; j < w; ++j) { int a; cin >> a; res += a; g.add_edge(s, h * w + h + j, a); for (int i = 0; i < h; ++i) { g.add_edge(h * w + h + j, i * w + j, inf); } } res -= g.solve(s, t, inf); cout << res << '\n'; }