結果

問題 No.1479 Matrix Eraser
ユーザー jupiro
提出日時 2021-04-16 20:38:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,804 bytes
コンパイル時間 2,088 ms
コンパイル使用メモリ 128,468 KB
最終ジャッジ日時 2025-01-20 18:58:51
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <array>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;


namespace KKT89
{
  template<typename T>
  struct Dinic {
      struct edge {
          int to;
          T cap;
          int rev;
          bool isrev;
          int idx;
          edge(int _to, T _cap, int _rev, bool _isrev, int _idx) :to(_to), cap(_cap), rev(_rev), isrev(_isrev), idx(_idx) {}
      };
      std::vector<std::vector<edge>> g;
      std::vector<int> min_cost, iter;
      T INF;
      Dinic(int n, T INF) :g(n), INF(INF) {}

      void add_edge(int from, int to, T cap, int idx = -1) {
          g[from].emplace_back(to, cap, (int)g[to].size(), false, idx);
          g[to].emplace_back(from, 0, (int)g[from].size() - 1, true, idx);
      }

      bool bfs(int s, int t) {
          min_cost.assign(g.size(), -1);
          std::queue<int> q;
          q.emplace(s);
          min_cost[s] = 0;
          while (!q.empty() && min_cost[t] == -1) {
              int cur = q.front();
              q.pop();
              for (auto& e : g[cur]) {
                  if (e.cap > 0 && min_cost[e.to] == -1) {
                      min_cost[e.to] = min_cost[cur] + 1;
                      q.push(e.to);
                  }
              }
          }
          return min_cost[t] != -1;
      }

      T dfs(int idx, const int t, T flow) {
          if (idx == t) return flow;
          for (int& i = iter[idx]; i < (int)g[idx].size(); i++) {
              edge& e = g[idx][i];
              if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
                  T d = dfs(e.to, t, std::min(flow, e.cap));
                  if (d > 0) {
                      e.cap -= d;
                      g[e.to][e.rev].cap += d;
                      return d;
                  }
              }
          }
          return 0;
      }

      T max_flow(int s, int t) {
          T flow = 0;
          while (bfs(s, t)) {
              iter.assign(g.size(), 0);
              T f = 0;
              while ((f = dfs(s, t, INF)) > 0) flow += f;
          }
          return flow;
      }

      void output() {
          for(int i = 0; i < (int)g.size(); i++) {
            for(auto &e : g[i]) {
              if(e.isrev) continue;
              auto &rev_e = g[e.to][e.rev];
              cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
          }
      }
  };
}
void solve()
{
  int H, W; cin >> H >> W;
  const int N = 500000;
  std::vector<std::vector<std::pair<int, int>>> vp(N + 1);
  for (int i = 0; i < H; ++i)
  {
    for (int j = 0; j < W; ++j)
    {
      int x; cin >> x;
      vp[x].emplace_back(i, j);
    }
  }
  int res = 0;
  for (int i = 1; i <= N; ++i)
  {
    if(vp[i].empty())
      continue;
    KKT89::Dinic g(H + W + 2, inf);
    const int s = H + W;
    const int t = s + 1;
    for(const auto &[h, w] : vp[i])
    {
      g.add_edge(h, H + w, 1);
    }
    for (int i = 0; i < H; ++i)
    {
      g.add_edge(s, i, 1);
    }
    for (int i = 0; i < W; ++i)
    {
      g.add_edge(H + i, t, 1);
    }
    res += g.max_flow(s, t);
  }
  cout << res << "\n";
}
int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int kkt = 1;
  //cin >> kkt;
  while(kkt--)
    solve();
  return 0;
}
0