結果
問題 | No.1479 Matrix Eraser |
ユーザー |
|
提出日時 | 2021-04-16 21:27:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 936 ms / 3,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 1,741 ms |
コンパイル使用メモリ | 103,212 KB |
最終ジャッジ日時 | 2025-01-20 19:30:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <atcoder/maxflow> #include <iostream> #include <vector> #include <set> using namespace std; constexpr int X = 500000; void solve() { int h, w; cin >> h >> w; vector<vector<pair<int, int>>> ess(X); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { int x; cin >> x; if (x > 0) ess[--x].emplace_back(i, j); } } int ans = 0; for (const auto& es : ess) { if (es.empty()) continue; atcoder::mf_graph<int> graph(h + w + 2); int s = h + w, g = s + 1; set<int> is, js; for (auto [i, j] : es) { is.insert(i); js.insert(j); graph.add_edge(i, h + j, 1); } for (auto i : is) graph.add_edge(s, i, 1); for (auto j : js) graph.add_edge(h + j, g, 1); ans += graph.flow(s, g); } cout << ans << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }