結果
| 問題 | No.957 植林 |
| ユーザー |
 QCFium
|
| 提出日時 | 2020-01-23 20:15:10 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,606 bytes |
| コンパイル時間 | 2,324 ms |
| コンパイル使用メモリ | 186,860 KB |
| 実行使用メモリ | 32,356 KB |
| 最終ジャッジ日時 | 2024-07-20 04:28:28 |
| 合計ジャッジ時間 | 34,262 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 WA * 11 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}/* copied from https://gist.github.com/MiSawa/9759784 *//* edited by QCFium */struct Dinic {private:typedef int64_t Cap;static const Cap INF = 1000000000000000000;struct LCNode {typedef LCNode *Ptr;Ptr ch[2], par, min_node;Cap val, min_val, lazy;int name;LCNode() : par(0), min_node(this), val(INF), min_val(INF), lazy(0) {ch[0] = ch[1] = 0;}inline void push() {if (lazy == 0) return;val += lazy; min_val += lazy;for (int i = 0; i < 2; i++) if (ch[i]) ch[i]->lazy += lazy;lazy = 0;}inline void update() {push();if (ch[0]) {min_val = ch[0]->min_val + ch[0]->lazy;min_node = ch[0]->min_node;}if (!ch[0] || min_val > val) {min_val = val; min_node = this;}if (ch[1] && min_val > ch[1]->min_val + ch[1]->lazy) {min_val = ch[1]->min_val + ch[1]->lazy;min_node = ch[1]->min_node;}}inline void set_value(Cap v) { expose(); val = v; update(); }inline Cap get_value() { expose(); return val; }inline Ptr get_min_node_on_path() { expose(); return min_node; }inline void add_to_path(Cap c) { expose(); lazy += c; push(); }inline int state() {if(par && par->ch[0] == this) return -1;if(par && par->ch[1] == this) return +1;return 0;}inline void rotate() {Ptr p = par; p->push(); push();bool lr = state()+1;if (p->state()) p->par->ch[p->state()>0] = this;par = p->par;p->ch[lr] = ch[!lr];if (ch[!lr]) ch[!lr]->par = p;(p->par = this)->ch[!lr] = p;p->update(); update();}inline void splay() {while (state()) {int s = state() * par->state();if (s) (s == 1 ? par : this)->rotate();rotate();}push();}inline void expose() {if (!par) return;for (Ptr p = this; p; p = p->par) p->splay();for (Ptr p = this; p->par; p = p->par) p->par->ch[1] = p;splay();}inline void cut() {expose();if (!ch[0]) return;ch[0]->par = 0;ch[0]->push();ch[0] = 0;update();}inline void link_to(Ptr p) {expose();par = p;}inline Ptr find_root() {expose();Ptr p = this;while (p->ch[0]) p = p->ch[0];p->expose();return p;}};struct E{int dst;Cap cap;int rev;E(int dst, Cap cap, int rev) : dst(dst), cap(cap), rev(rev) {}};int n;std::vector<std::vector<E> > g;std::vector<int> level, active;std::vector<LCNode> lc;inline void unuse_edge(E &e) {E &ee = g[e.dst][e.rev]; int u = ee.dst;Cap use = ee.cap - lc[u].get_value();e.cap += use; ee.cap -= use;active[u] = false;lc[u].cut(); lc[u].set_value(INF);}inline void init(){lc.resize(n);active.assign(n, false);for (int i = 0; i < n; i++) lc[i].name = i;}Cap dfs(const int &s, const int &t) {std::vector<int> iter(n);for (int i = 0; i < n; i++) iter[i] = (int) (g[i].size()) - 1;Cap res = 0;while(1){const int &u = lc[t].find_root()->name;if (u == s) {Cap f = lc[t].get_min_node_on_path()->get_value();res += f;lc[t].add_to_path(-f);while (1) {int v = lc[t].get_min_node_on_path()->name;Cap f = lc[v].get_value();if (f > 0) break;unuse_edge(g[v][iter[v]]);}} else {for (int &i = iter[u]; i >= 0; --i) {E &e = g[u][i], &ee = g[e.dst][e.rev]; int v = e.dst;if (level[u]-1 != level[v] || ee.cap <= 0) continue;active[u] = true;lc[u].set_value(ee.cap);lc[u].link_to(&lc[v]);break;}if (active[u]) continue;if (u == t) break;level[u] = -1;for (auto& e : g[u]) if (active[e.dst] && iter[e.dst] == e.rev)unuse_edge(g[e.dst][e.rev]);}}for (int i = 0; i < n; i++) if (active[i]) unuse_edge(g[i][iter[i]]);return res;}public:Dinic(int n) : n(n), g(n) {}inline void add_hen(int src, int dst, Cap cap, bool direct) {if (src == dst) return;g[src].push_back(E(dst,cap,g[dst].size()));g[dst].push_back(E(src,direct?0:cap ,g[src].size() - 1));}Cap run(int s, int t) { // O(NMlogN)init();std::vector<int> q(n);for (Cap flow = 0; ;) {level.assign(n, -1);int ql = 0, qr = 0;level[q[qr++] = s] = 0;while (ql != qr && level[t] == -1) {int u = q[ql++];for (auto& e : g[u]) if (e.cap > 0 && level[e.dst] == -1)level[ q[qr++] = e.dst ] = level[u] + 1;}if (level[t] == -1) return flow;flow += dfs(s, t);}}};int main() {int h = ri();int w = ri();int a[h][w];for (auto &i : a) for (auto &j : i) j = ri();int b[h];for (auto &i : b) i = ri();int c[w];for (auto &i : c) i = ri();Dinic dinic(h + w + h * w + 2);int goal = h + w + h * w + 1;int64_t base = 0;for (int i = 0; i < h; i++) {int64_t cost = std::accumulate(a[i], a[i] + w, 0LL) - b[i];if (cost < 0) base += cost;dinic.add_hen(0, i + 1, std::max<int64_t>(0, cost), true);dinic.add_hen(i + 1, goal, std::max<int64_t>(0, -cost), true);}for (int i = 0; i < w; i++) {int64_t cost = -c[i];for (int j = 0; j < h; j++) cost += a[j][i];dinic.add_hen(0, h + 1 + i, std::max<int64_t>(0, cost), true);dinic.add_hen(h + 1 + i, goal, std::max<int64_t>(0, -cost), true);}for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {base += -a[i][j];dinic.add_hen(i + 1, h + w + i * w + j + 1, 10000000000000000, true);dinic.add_hen(h + j + 1, h + w + i * w + j + 1, 10000000000000000, true);dinic.add_hen(h + w + i * w + j + 1, goal, a[i][j], true);}std::cout << std::max<int64_t>(0, -(base + dinic.run(0, goal))) << std::endl;return 0;}