結果

問題 No.957 植林
ユーザー risujirohrisujiroh
提出日時 2019-12-19 23:02:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,490 bytes
コンパイル時間 1,780 ms
コンパイル使用メモリ 179,120 KB
実行使用メモリ 23,880 KB
最終ジャッジ日時 2023-09-21 07:37:17
合計ジャッジ時間 11,028 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
8,756 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 730 ms
21,548 KB
testcase_04 AC 616 ms
20,160 KB
testcase_05 AC 375 ms
22,656 KB
testcase_06 AC 747 ms
23,724 KB
testcase_07 AC 758 ms
21,304 KB
testcase_08 AC 206 ms
22,108 KB
testcase_09 AC 212 ms
21,932 KB
testcase_10 AC 235 ms
23,076 KB
testcase_11 AC 244 ms
22,200 KB
testcase_12 AC 249 ms
22,416 KB
testcase_13 AC 161 ms
20,276 KB
testcase_14 AC 190 ms
23,880 KB
testcase_15 AC 159 ms
21,660 KB
testcase_16 AC 146 ms
20,032 KB
testcase_17 AC 151 ms
21,208 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  vector< vector<int> > g(h, vector<int>(w));
  for (auto&& v : g) {
    for (auto&& e : v) {
      cin >> e;
    }
  }
  vector<int> r(h);
  for (auto&& e : r) {
    cin >> e;
  }
  vector<int> c(w);
  for (auto&& e : c) {
    cin >> e;
  }
  int s = h + w + h * w, t = s + 1;
  Dinic<long long> d(t + 1);
  long long res = 0;
  for (int i = 0; i < h; ++i) {
    long long sg = 0;
    for (int j = 0; j < w; ++j) {
      sg += g[i][j];
    }
    res += r[i];
    d.add_edge(s, i, r[i]);
    d.add_edge(i, t, sg);
  }
  for (int j = 0; j < w; ++j) {
    long long sg = 0;
    for (int i = 0; i < h; ++i) {
      sg += g[i][j];
    }
    res += c[j];
    d.add_edge(s, h + j, c[j]);
    d.add_edge(h + j, t, sg);
  }
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      int v = h + w + i * w + j;
      res += g[i][j];
      d.add_edge(s, v, g[i][j]);
      d.add_edge(v, i, inf);
      d.add_edge(v, h + j, inf);
    }
  }
  res -= d.solve(s, t, inf);
  cout << res << '\n';
}
0