結果
| 問題 |
No.1640 簡単な色塗り
|
| コンテスト | |
| ユーザー |
 ei1333333
|
| 提出日時 | 2021-08-06 23:21:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 134 ms / 2,000 ms |
| コード長 | 8,476 bytes |
| コンパイル時間 | 2,414 ms |
| コンパイル使用メモリ | 211,276 KB |
| 最終ジャッジ日時 | 2025-01-23 16:12:42 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
os << p.first << " " << p.second;
return os;
}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
is >> p.first >> p.second;
return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
for(int i = 0; i < (int) v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
for(T &in : v) is >> in;
return is;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T = int64 >
vector< T > make_v(size_t a) {
return vector< T >(a);
}
template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}
template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
t = v;
}
template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
template< typename F >
struct FixPoint : F {
FixPoint(F &&f) : F(forward< F >(f)) {}
template< typename... Args >
decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, forward< Args >(args)...);
}
};
template< typename F >
inline decltype(auto) MFP(F &&f) {
return FixPoint< F >{forward< F >(f)};
}
/**
* @brief Bipartite-Flow(二部グラフのフロー)
* @docs docs/bipartite-flow.md
*/
struct BipartiteFlow {
size_t n, m, time_stamp;
vector< vector< int > > g, rg;
vector< int > match_l, match_r, dist, used, alive;
bool matched;
public:
explicit BipartiteFlow(size_t n, size_t m) :
n(n), m(m), g(n), rg(m), match_l(n, -1), match_r(m, -1), used(n), alive(n, 1), time_stamp(0), matched(false) {}
void add_edge(int u, int v) {
g[u].push_back(v);
rg[v].emplace_back(u);
}
vector< pair< int, int > > max_matching() {
matched = true;
for(;;) {
build_augment_path();
++time_stamp;
int flow = 0;
for(int i = 0; i < n; i++) {
if(match_l[i] == -1) flow += find_min_dist_augment_path(i);
}
if(flow == 0) break;
}
vector< pair< int, int > > ret;
for(int i = 0; i < n; i++) {
if(match_l[i] >= 0) ret.emplace_back(i, match_l[i]);
}
return ret;
}
/* http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0334 */
vector< pair< int, int > > lex_max_matching() {
if(!matched) max_matching();
for(auto &vs : g) sort(begin(vs), end(vs));
vector< pair< int, int > > es;
for(int i = 0; i < n; i++) {
if(match_l[i] == -1 || alive[i] == 0) {
continue;
}
match_r[match_l[i]] = -1;
match_l[i] = -1;
++time_stamp;
find_augment_path(i);
alive[i] = 0;
es.emplace_back(i, match_l[i]);
}
return es;
}
vector< int > min_vertex_cover() {
auto visited = find_residual_path();
vector< int > ret;
for(int i = 0; i < n + m; i++) {
if(visited[i] ^ (i < n)) {
ret.emplace_back(i);
}
}
return ret;
}
/* https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11 */
vector< int > lex_min_vertex_cover(const vector< int > &ord) {
assert(ord.size() == n + m);
auto res = build_risidual_graph();
vector< vector< int > > r_res(n + m + 2);
for(int i = 0; i < n + m + 2; i++) {
for(auto &j : res[i]) r_res[j].emplace_back(i);
}
queue< int > que;
vector< int > visited(n + m + 2, -1);
auto expand_left = [&](int t) {
if(visited[t] != -1) return;
que.emplace(t);
visited[t] = 1;
while(!que.empty()) {
int idx = que.front();
que.pop();
for(auto &to : r_res[idx]) {
if(visited[to] != -1) continue;
visited[to] = 1;
que.emplace(to);
}
}
};
auto expand_right = [&](int t) {
if(visited[t] != -1) return;
que.emplace(t);
visited[t] = 0;
while(!que.empty()) {
int idx = que.front();
que.pop();
for(auto &to : res[idx]) {
if(visited[to] != -1) continue;
visited[to] = 0;
que.emplace(to);
}
}
};
expand_right(n + m);
expand_left(n + m + 1);
vector< int > ret;
for(auto &t : ord) {
if(t < n) {
expand_left(t);
if(visited[t] & 1) ret.emplace_back(t);
} else {
expand_right(t);
if(~visited[t] & 1) ret.emplace_back(t);
}
}
return ret;
}
vector< int > max_independent_set() {
auto visited = find_residual_path();
vector< int > ret;
for(int i = 0; i < n + m; i++) {
if(visited[i] ^ (i >= n)) {
ret.emplace_back(i);
}
}
return ret;
}
vector< pair< int, int > > min_edge_cover() {
auto es = max_matching();
for(int i = 0; i < n; i++) {
if(match_l[i] >= 0) {
continue;
}
if(g[i].empty()) {
return {};
}
es.emplace_back(i, g[i][0]);
}
for(int i = 0; i < m; i++) {
if(match_r[i] >= 0) {
continue;
}
if(rg[i].empty()) {
return {};
}
es.emplace_back(rg[i][0], i);
}
return es;
}
// left: [0,n), right: [n,n+m), S: n+m, T: n+m+1
vector< vector< int > > build_risidual_graph() {
if(!matched) max_matching();
const size_t S = n + m;
const size_t T = n + m + 1;
vector< vector< int > > ris(n + m + 2);
for(int i = 0; i < n; i++) {
if(match_l[i] == -1) ris[S].emplace_back(i);
else ris[i].emplace_back(S);
}
for(int i = 0; i < m; i++) {
if(match_r[i] == -1) ris[i + n].emplace_back(T);
else ris[T].emplace_back(i + n);
}
for(int i = 0; i < n; i++) {
for(auto &j : g[i]) {
if(match_l[i] == j) ris[j + n].emplace_back(i);
else ris[i].emplace_back(j + n);
}
}
return ris;
}
private:
vector< int > find_residual_path() {
auto res = build_risidual_graph();
queue< int > que;
vector< int > visited(n + m + 2);
que.emplace(n + m);
visited[n + m] = true;
while(!que.empty()) {
int idx = que.front();
que.pop();
for(auto &to : res[idx]) {
if(visited[to]) continue;
visited[to] = true;
que.emplace(to);
}
}
return visited;
}
void build_augment_path() {
queue< int > que;
dist.assign(g.size(), -1);
for(int i = 0; i < n; i++) {
if(match_l[i] == -1) {
que.emplace(i);
dist[i] = 0;
}
}
while(!que.empty()) {
int a = que.front();
que.pop();
for(auto &b : g[a]) {
int c = match_r[b];
if(c >= 0 && dist[c] == -1) {
dist[c] = dist[a] + 1;
que.emplace(c);
}
}
}
}
bool find_min_dist_augment_path(int a) {
used[a] = time_stamp;
for(auto &b : g[a]) {
int c = match_r[b];
if(c < 0 || (used[c] != time_stamp && dist[c] == dist[a] + 1 && find_min_dist_augment_path(c))) {
match_r[b] = a;
match_l[a] = b;
return true;
}
}
return false;
}
bool find_augment_path(int a) {
used[a] = time_stamp;
for(auto &b : g[a]) {
int c = match_r[b];
if(c < 0 || (alive[c] == 1 && used[c] != time_stamp && find_augment_path(c))) {
match_r[b] = a;
match_l[a] = b;
return true;
}
}
return false;
}
};
int main() {
int N;
cin >> N;
BipartiteFlow flow(N, N);
for(int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
--x, --y;
flow.add_edge(i, x);
flow.add_edge(i, y);
}
auto ret = flow.max_matching();
if(ret.size() < N) {
cout << "No\n";
} else {
cout << "Yes\n";
for(auto &p : ret) {
cout << p.second + 1 << "\n";
}
}
}