結果
問題 | No.483 マッチ並べ |
ユーザー | tubo28 |
提出日時 | 2017-02-10 22:55:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,146 bytes |
コンパイル時間 | 1,891 ms |
コンパイル使用メモリ | 173,916 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-29 08:12:29 |
合計ジャッジ時間 | 5,006 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FOR(i, a, b) for (int i = (a); i < int(b); ++i) #define RFOR(i, a, b) for (int i = (b) - 1; i >= int(a); --i) #define rep(i, n) FOR(i, 0, n) #define rep1(i, n) FOR(i, 1, int(n) + 1) #define rrep(i, n) RFOR(i, 0, n) #define rrep1(i, n) RFOR(i, 1, int(n) + 1) #define all(c) begin(c), end(c) template<typename T> void __dump__(const T &first){ std::cerr << first << std::endl; } template<typename First, typename... Rest> void __dump__(const First& first, const Rest&... rest) { std::cerr << first << ", "; __dump__(rest...); } #define dump(...) { std::cerr << __LINE__ << ":\t" #__VA_ARGS__ " = "; __dump__(__VA_ARGS__); } const int R = 120; const int C = 120; const int N = R*C; class bipartite_matching { public: int n; vector<vector<int>> g; vector<int> match; bipartite_matching(int n_) : n(n_), g(n_), match(n_), used(n_) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } int maximum_matching(void) { int res = 0; fill(begin(match), end(match), -1); for (int v = 0; v < n; ++v) { if (match[v] == -1) { fill(begin(used), end(used), false); if (dfs(v)) res++; } } return res; } private: vector<int> used; bool dfs(int v) { used[v] = true; for (int u : g[v]) { int w = match[u]; if (w == -1 || (!used[w] && dfs(w))) { match[v] = u; match[u] = v; return true; } } return false; } }; int enc(int r, int c){ return r*C + c; } int main(){ int n; while(cin >> n){ bipartite_matching bm(N + 100); rep(i, n){ int r, c, rr, cc; cin >> r >> c >> rr >> cc; --r, --c, --rr, --cc; int x = enc(r, c), y = enc(rr, cc); bm.add_edge(i, x + 100); bm.add_edge(i, y + 100); } int f = bm.maximum_matching(); dump(f); puts(f == n ? "YES" : "NO"); } }