結果
問題 | No.957 植林 |
ユーザー | nebukuro09 |
提出日時 | 2019-12-20 14:30:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 2,967 bytes |
コンパイル時間 | 2,079 ms |
コンパイル使用メモリ | 179,168 KB |
実行使用メモリ | 12,432 KB |
最終ジャッジ日時 | 2023-09-22 18:06:13 |
合計ジャッジ時間 | 16,901 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 25 ms
11,160 KB |
testcase_04 | AC | 26 ms
10,940 KB |
testcase_05 | AC | 24 ms
11,576 KB |
testcase_06 | AC | 34 ms
11,820 KB |
testcase_07 | AC | 26 ms
10,892 KB |
testcase_08 | AC | 19 ms
11,504 KB |
testcase_09 | AC | 19 ms
11,316 KB |
testcase_10 | AC | 20 ms
11,712 KB |
testcase_11 | AC | 19 ms
11,560 KB |
testcase_12 | AC | 19 ms
11,240 KB |
testcase_13 | AC | 16 ms
9,696 KB |
testcase_14 | AC | 19 ms
11,804 KB |
testcase_15 | AC | 18 ms
11,240 KB |
testcase_16 | AC | 16 ms
9,676 KB |
testcase_17 | AC | 18 ms
11,032 KB |
testcase_18 | AC | 433 ms
11,464 KB |
testcase_19 | AC | 449 ms
11,576 KB |
testcase_20 | AC | 484 ms
11,884 KB |
testcase_21 | AC | 509 ms
11,796 KB |
testcase_22 | AC | 522 ms
12,108 KB |
testcase_23 | AC | 557 ms
12,372 KB |
testcase_24 | AC | 590 ms
12,280 KB |
testcase_25 | AC | 632 ms
12,216 KB |
testcase_26 | AC | 619 ms
12,276 KB |
testcase_27 | AC | 619 ms
12,320 KB |
testcase_28 | AC | 620 ms
12,244 KB |
testcase_29 | AC | 625 ms
12,224 KB |
testcase_30 | AC | 600 ms
12,348 KB |
testcase_31 | AC | 431 ms
11,296 KB |
testcase_32 | AC | 453 ms
11,428 KB |
testcase_33 | AC | 480 ms
11,808 KB |
testcase_34 | AC | 506 ms
11,672 KB |
testcase_35 | AC | 524 ms
12,112 KB |
testcase_36 | AC | 554 ms
12,324 KB |
testcase_37 | AC | 584 ms
12,220 KB |
testcase_38 | AC | 618 ms
12,280 KB |
testcase_39 | AC | 624 ms
12,432 KB |
testcase_40 | AC | 621 ms
12,212 KB |
testcase_41 | AC | 16 ms
12,212 KB |
testcase_42 | AC | 16 ms
12,240 KB |
testcase_43 | AC | 25 ms
12,292 KB |
testcase_44 | AC | 28 ms
12,276 KB |
testcase_45 | AC | 2 ms
4,376 KB |
testcase_46 | AC | 2 ms
4,380 KB |
testcase_47 | AC | 1 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; #define fst first #define snd second #define all(c) ((c).begin()), ((c).end()) const long long INF = (1ll << 50); struct graph { typedef long long flow_type; struct edge { int src, dst; flow_type capacity, flow; size_t rev; }; int n; vector<vector<edge>> adj; graph(int n) : n(n), adj(n) { } void add_edge(int src, int dst, ll capacity) { adj[src].push_back({src, dst, capacity, 0, adj[dst].size()}); adj[dst].push_back({dst, src, 0, 0, adj[src].size() - 1}); } flow_type max_flow(int s, int t) { vector<flow_type> excess(n); vector<int> dist(n), active(n), count(2*n); queue<int> Q; auto enqueue = [&](int v) { if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } }; auto push = [&](edge &e) { flow_type f = min(excess[e.src], e.capacity - e.flow); if (dist[e.src] <= dist[e.dst] || f == 0) return; e.flow += f; adj[e.dst][e.rev].flow -= f; excess[e.dst] += f; excess[e.src] -= f; enqueue(e.dst); }; dist[s] = n; active[s] = active[t] = true; count[0] = n-1; count[n] = 1; for (int u = 0; u < n; ++u) for (auto &e: adj[u]) e.flow = 0; for (auto &e: adj[s]) { excess[s] += e.capacity; push(e); } while (!Q.empty()) { int u = Q.front(); Q.pop(); active[u] = false; for (auto &e: adj[u]) push(e); if (excess[u] > 0) { if (count[dist[u]] == 1) { int k = dist[u]; // Gap Heuristics for (int v = 0; v < n; v++) { if (dist[v] < k) continue; count[dist[v]]--; dist[v] = max(dist[v], n+1); count[dist[v]]++; enqueue(v); } } else { count[dist[u]]--; // Relabel dist[u] = 2*n; for (auto &e: adj[u]) if (e.capacity > e.flow) dist[u] = min(dist[u], dist[e.dst] + 1); count[dist[u]]++; enqueue(u); } } } flow_type flow = 0; for (auto e: adj[s]) flow += e.flow; return flow; } }; ll A[303][303]; ll R[303]; ll C[303]; void solve() { int H, W; cin >> H >> W; REP(i, H) REP(j, W) cin >> A[i][j]; REP(i, H) cin >> R[i]; REP(j, W) cin >> C[j]; graph g(H+W+2); int source = H + W; int sink = H + W + 1; REP(i, H) { ll s = 0; REP(j, W) s += A[i][j]; g.add_edge(source, i, s); g.add_edge(i, sink, R[i]); } REP(j, W) { g.add_edge(H+j, sink, C[j]); } REP(i, H) REP(j, W) { g.add_edge(i, H+j, A[i][j]); } ll ans = 0; REP(i, H) ans += R[i]; REP(j, W) ans += C[j]; ans -= g.max_flow(source, sink); cout << ans << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); solve(); }