結果

問題 No.957 植林
コンテスト
ユーザー hitonanode
提出日時 2019-12-19 23:22:16
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 6,841 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,894 ms
コンパイル使用メモリ 181,412 KB
実行使用メモリ 31,512 KB
最終ジャッジ日時 2024-07-07 02:06:44
合計ジャッジ時間 48,858 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
///// This part below is only for debug, not used /////
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
///// END /////

#define int long long
// <https://tjkendev.github.io/procon-library/cpp/max_flow/push-relabel-highest.html>
#define N 300*300 + 600 + 2 + 10

class PushRelabel {
  const lint inf = 1e18;
  int n;
  struct Edge {
    int to, cap, rev;
  };
  vector<Edge> g[N];

  int qs[N];
  int hs[N], ds[N], fs[N];
  bool active[N];
  vector<int> bs[N];
  int cur;

public:
  PushRelabel() {}
  PushRelabel(int n) { init(n); }
  inline void init(int n) { this->n = n; }

  inline void add_edge(int fr, int to, int cap) {
    g[fr].emplace_back(Edge{to, cap, (int) g[to].size()});
    g[to].emplace_back(Edge{fr, 0, (int) g[fr].size()-1});
  }

  inline int bfs(int t) {
    int a = 0, b = 1;
    for(int i=0; i<n; ++i) hs[i] = n, ds[i] = 0, bs[i].clear();
    qs[0] = t;
    hs[t] = 0; ds[0] = 1;
    cur = 0;
    int d = 0;
    while(a < b) {
      int v = qs[a++];
      d = hs[v];
      for(Edge &e : g[v]) {
        int w = e.to;
        if(hs[w] <= d + 1 || g[w][e.rev].cap == 0) continue;
        hs[w] = d + 1;
        if(active[w] && d+1 < n) {
          bs[d+1].push_back(w);
          cur = d+1;
        }
        if(d+1 < n) ++ds[d+1];
        qs[b++] = w;
      }
    }
    return d+1;
  }

  inline int flow(int s, int t) {
    for(int i=0; i<n; ++i) fs[i] = 0, active[i] = false;

    fs[s] = inf;
    active[s] = true;

    // initialize hs, bs, ds
    int gap = bfs(t);
    bs[cur].push_back(s);

    int cnt = 0;
    while(1) {
      while(cur >= 0 && bs[cur].size() == 0) --cur;
      if(cur < 0) break;

      int v = bs[cur].back(); bs[cur].pop_back();
      if(v == t) continue;

      int hv = hs[v];
      // Gap-relabeling
      if(hv > gap) {
        if(hv < n) --ds[hv];
        hs[v] = n;
        continue;
      }


      // push
      int rest = fs[v];
      for(Edge &e : g[v]) {
        int w = e.to;
        if(e.cap > 0 && hv > hs[w] && hs[w] < gap) {
          int d = min(rest, e.cap);
          e.cap -= d;
          g[w][e.rev].cap += d;
          rest -= d;
          fs[w] += d;
          if(!active[w]) {
            int hw = hs[w];
            bs[hw].push_back(w);
            if(cur < hw) cur = hw;
            active[w] = true;
          }
          if(rest == 0) break;
        }
      }
      fs[v] = rest;

      if(rest == 0) {
        active[v] = false;
        continue;
      }

      // relabel
      int h0 = hs[v];
      hv = n;
      for(Edge &e : g[v]) {
        int w = e.to;
        if(e.cap > 0 && hv > hs[w] + 1 && hs[w] < gap) {
          hv = hs[w] + 1;
        }
      }
      if(h0 != hv) {
        --ds[h0];
        if(ds[h0] == 0 && h0 < gap) {
          gap = h0;
          hv = n;
        } else if(hv == gap) {
          ++gap;
        }
        if(hv < n) ++ds[hv];
      }

      hs[v] = hv;
      if(hv < n) {
        bs[hv].push_back(v);
        if(cur < hv) cur = hv;
      } else {
        active[v] = false;
      }

      if((++cnt) % n == 0) {
        gap = bfs(t);
      }
    }
    return fs[t];
  }

};
PushRelabel g;

signed main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<lint>> G(H, vector<lint>(W));
    cin >> G;
    vector<lint> R(H), C(W);
    cin >> R >> C;
    int Z = 1 + H + W + H * W;
    g.init(Z + 1);
    REP(i, H) if (R[i]) g.add_edge(0, i + 1,R[i]);
    REP(j, W) if (C[j]) g.add_edge(0, H + 1 + j, C[j]);
    REP(i, H) REP(j, W) {
        int b = H + W + 1 + i * W + j;
        if (G[i][j] < R[i] + C[j])
        {
            g.add_edge(i + 1, b, 1e10);
            g.add_edge(H + 1 + j, b, 1e10);
            g.add_edge(b, Z, G[i][j]);
        }
        else
        {
            g.add_edge(i + 1, Z, 1e10);
            g.add_edge(H + j + 1, Z, 1e10);
        }
    }
    lint f = g.flow(0, Z);
    cout << accumulate(ALL(R), 0LL) + accumulate(ALL(C), 0LL) - f << endl;
}
0