結果
問題 | No.957 植林 |
ユーザー | outline |
提出日時 | 2021-02-28 19:05:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,907 bytes |
コンパイル時間 | 1,752 ms |
コンパイル使用メモリ | 152,800 KB |
実行使用メモリ | 27,784 KB |
最終ジャッジ日時 | 2024-10-02 21:52:48 |
合計ジャッジ時間 | 6,811 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 100 ms
21,856 KB |
testcase_04 | AC | 80 ms
20,392 KB |
testcase_05 | AC | 89 ms
22,428 KB |
testcase_06 | AC | 99 ms
23,408 KB |
testcase_07 | AC | 102 ms
21,096 KB |
testcase_08 | AC | 61 ms
22,336 KB |
testcase_09 | AC | 57 ms
22,508 KB |
testcase_10 | AC | 66 ms
23,188 KB |
testcase_11 | AC | 62 ms
22,404 KB |
testcase_12 | AC | 62 ms
22,300 KB |
testcase_13 | AC | 47 ms
19,720 KB |
testcase_14 | AC | 58 ms
24,264 KB |
testcase_15 | AC | 55 ms
22,124 KB |
testcase_16 | AC | 46 ms
19,688 KB |
testcase_17 | AC | 49 ms
20,976 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 <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}template<typename flow_t>struct Dinic{const flow_t INF;struct Edge{int to;flow_t cap;int rev;bool isrev;Edge(int to, flow_t cap, int rev, bool isrev) : to(to), cap(cap), rev(rev), isrev(isrev) {}};vector<vector<Edge>> graph;vector<int> min_cost; // sからの距離(bfsで調べる)vector<int> iter; // どこまで調べ終わったか(dfs時に使用)Dinic(int V) : INF(numeric_limits<flow_t>::max() / 2){graph.resize(V);}void add_edge(int from, int to, flow_t cap){graph[from].push_back(Edge(to, cap, graph[to].size(), false));graph[to].push_back(Edge(from, 0, graph[from].size() - 1, true));}// 最短路探索bool bfs(int s, int t){min_cost.assign(graph.size(), -1);queue<int> que;min_cost[s] = 0;que.push(s);while(!que.empty() && min_cost[t] == -1){int p = que.front();que.pop();for(auto &e : graph[p]){if(e.cap > 0 && min_cost[e.to] == -1){min_cost[e.to] = min_cost[p] + 1;que.push(e.to);}}}return min_cost[t] != -1;}flow_t dfs(int v, int t, flow_t flow){if(v == t) return flow;for(int &i = iter[v]; i < (int)graph[v].size(); ++i){Edge &e = graph[v][i];if(e.cap > 0 && min_cost[v] < min_cost[e.to]){flow_t d = dfs(e.to, t, min(flow, e.cap));if(d > 0){e.cap -= d;graph[e.to][e.rev].cap += d;return d;}}}return 0;}flow_t max_flow(int s, int t){flow_t flow = 0;// 最短路を求めて、そのパスに最大流を流すwhile(bfs(s, t)){iter.assign(graph.size(), 0);flow_t f = 0;while((f = dfs(s, t, INF)) > 0) flow += f;}return flow;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int H, W;cin >> H >> W;vector<vector<ll>> G(H, vector<ll>(W));int s = H * W + H + W, t = s + 1, V = s + 2;Dinic<ll> g(V);ll ans = 0;for(int i = 0; i < H; ++i){for(int j = 0; j < W; ++j){cin >> G[i][j];int v = i * W + j;g.add_edge(v, t, G[i][j]);int w = H * W + i, x = H * W + H + j;g.add_edge(w, v, INF);g.add_edge(x, v, INF);}}vector<ll> R(H), C(W);for(int i = 0; i < H; ++i){cin >> R[i];ans += R[i];int v = H * W + i;g.add_edge(s, v, R[i]);}for(int i = 0; i < W; ++i){cin >> C[i];ans += C[i];int v = H * W + H + i;g.add_edge(s, v, C[i]);}ans -= g.max_flow(s, t);cout << ans << endl;return 0;}