結果
問題 | No.957 植林 |
ユーザー |
|
提出日時 | 2019-12-20 14:30:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 594 ms / 2,000 ms |
コード長 | 2,967 bytes |
コンパイル時間 | 1,998 ms |
コンパイル使用メモリ | 181,228 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-07-08 09:25:29 |
合計ジャッジ時間 | 16,477 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#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(); }