結果

問題 No.957 植林
ユーザー bokusunny
提出日時 2022-01-19 14:41:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,444 bytes
コンパイル時間 2,558 ms
コンパイル使用メモリ 211,548 KB
最終ジャッジ日時 2025-01-27 13:06:29
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 TLE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define bokusunny ios::sync_with_stdio(false), cin.tie(nullptr);

#include <atcoder/maxflow>
using namespace atcoder;

void solve() {
  int H, W;
  cin >> H >> W;
  vector Cost(H, vector<long long>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> Cost[i][j];
    }
  }
  vector<long long> R(H), C(W);
  for (int i = 0; i < H; i++) cin >> R[i];
  for (int i = 0; i < W; i++) cin >> C[i];

  using Cap = long long;
  mf_graph<Cap> G(H * W + H + W + 2);
  const int s = H * W + H + W;
  const int g = H * W + H + W + 1;
  const long long INF = 1LL << 60;

  auto to_num = [&](int h, int w) { return h * W + w; };

  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      G.add_edge(s, to_num(h, w), 0);
      G.add_edge(to_num(h, w), g, Cost[h][w]);
    }
  }
  for (int h = 0; h < H; h++) {
    int cur = H * W + h;
    G.add_edge(s, cur, R[h]);
    G.add_edge(cur, g, 0);
    for (int w = 0; w < W; w++) {
      G.add_edge(cur, to_num(h, w), INF);
    }
  }
  for (int w = 0; w < W; w++) {
    int cur = H * W + H + w;
    G.add_edge(s, cur, C[w]);
    G.add_edge(cur, g, 0);
    for (int h = 0; h < H; h++) {
      G.add_edge(cur, to_num(h, w), INF);
    }
  }

  long long all = accumulate(R.begin(), R.end(), 0LL) + accumulate(C.begin(), C.end(), 0LL);
  cout << all - G.flow(s, g) << endl;
}

int main() {
  bokusunny;
  solve();

  return 0;
}
0