人类智慧题
A - Train Splitting
https://www.luogu.com.cn/problem/CF1776F
神秘构造题，猜 \(k=2\) 一定能构造
考虑直接从图上抠一个点下来，与之相关的边全部染成 1，剩下的染成 2
发现如果恰好选中了菊花的根就不行
需要找到一个度数不为 \(n-1\) 的点。完全图的话，从菊花的根上抠一条当颜色 3 即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> deg(n + 1);
std::vector<std::pair<int, int> > e(m + 1);
int pos = -1;
for (int i = 1; i <= m; ++i) {
std::cin >> e[i].first >> e[i].second;
++deg[e[i].first], ++deg[e[i].second];
}
for (int i = 1; i <= n; ++i)
if (deg[i] != n - 1) {
pos = i;
break;
}
if (pos != -1) {
std::cout << 2 << '\n';
for (int i = 1; i <= m; ++i)
if (e[i].first == pos || e[i].second == pos)
std::cout << 1 << ' ';
else
std::cout << 2 << ' ';
std::cout << '\n';
}
else {
std::cout << 3 << '\n';
pos = 1;
bool flag = true;
for (int i = 1; i <= m; ++i)
if (e[i].first == pos || e[i].second == pos) {
if (flag)
std::cout << 3 << ' ', flag = false;
else
std::cout << 1 << ' ';
}
else
std::cout << 2 << ' ';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Graph Partition
https://www.luogu.com.cn/problem/AT_agc039_b
- 考虑二分图染色什么时候不行，即有奇环时
- 考虑有多少种颜色时能染奇环，发现都不行，故二分图染色即可判定。
真的只有绿吗？观察样例，猜测答案为图的直径。考虑构造：
枚举每个点并钦定其为唯一一个 \(1\)，然后依次向下染色。显然最后构造出来的是合法的。最大为直径长度 + 1。
也可以从差分约束的角度理解，但无甚必要。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g(n + 1), g1(n + 1, std::vector<int> (n + 1, 0x3f3f3f3f));
for (int i = 1; i <= n; ++i) {
g1[i][i] = 0;
for (int j = 1; j <= n; ++j) {
char t;
std::cin >> t;
if (t == '1')
g[i].push_back(j), g1[i][j] = 1;
}
}
std::vector<int> col(n + 1);
std::function<bool(int, int)> DFS = [&](int x, int now) {
col[x] = now;
for (auto i : g[x])
if (!col[i]) {
if (!DFS(i, 3 - now))
return false;
}
else if (col[i] == now)
return false;
return true;
};
if (!DFS(1, 1))
std::cout << -1 << '\n';
else {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
g1[i][j] = std::min(g1[i][j], g1[i][k] + g1[k][j]);
int mx = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mx = std::max(mx, g1[i][j] + 1);
std::cout << mx << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C - Strange Housing
https://www.luogu.com.cn/problem/CF1470D
- 第一反应是随便找一个生成树然后二分图染色，但是发现有当且仅当奇环时行为不太正确
- 考虑打个补丁，抛弃二分图染色的想法，不断尝试染成黑色，如果染了下一个点会出现黑黑边，那就不染它，对得比较显然。
- 当且仅当不连通时无解。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
std::vector<std::vector<int> > g(n + 1), g1(n + 1);
int cnt = 0;
for (int x, y; m--; ) {
std::cin >> x >> y;
g1[x].push_back(y), g1[y].push_back(x);
if (find(x) != find(y)) {
f[find(x)] = find(y);
++cnt, g[x].push_back(y), g[y].push_back(x);
}
}
if (cnt != n - 1) {
std::cout << "NO\n";
continue;
}
std::vector<int> col(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
for (auto i : g[x])
if (i != fa) {
bool flag = true;
for (auto j : g1[i])
if (col[j] == 2) {
flag = false;
break;
}
if (flag)
col[i] = 2;
else
col[i] = 1;
DFS(i, x);
}
return;
};
col[1] = 2, DFS(1, -1);
std::vector<int> res;
for (int i = 1; i <= n; ++i)
if (col[i] == 2)
res.push_back(i);
std::cout << "YES\n" << (int)res.size() << '\n';
for (auto i : res)
std::cout << i << ' ';
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D - Defender of Childhood Dreams
https://www.luogu.com.cn/problem/CF1583F
考虑把每连续 \(k\) 个点分为一个一级组，每个一级组内全部连 \(1\) 边。显然组内边最长不超过 \(k-1\)。
接着把每连续 \(k\) 个一级组分为一个二级组，二级组内空闲边全部涂成颜色 \(2\)。
此时 \(a<b\) 的条件就会派上用场：每个一级组的值域是没有交的，一级组之间的边都是同一个朝向。
这样就保证由颜色为 \(2\) 的边构成的连链来自不同的一级组，长度最多为 \(k-1\)。
依次类推，\(i\) 级组是大小为 \(k^i\) 的团，故 \(i\) 最大为 \(\left\lceil \log_kn\right\rceil\)。
按上述流程构造，即可 \(O(n^2)\) 完成。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k;
std::cin >> n >> k;
using arr = std::vector<int>;
using brr = std::vector<arr>;
brr pos;
for (int i = 1; i <= n; ++i)
pos.push_back({ i });
brr g(n + 1, arr(n + 1));
std::function<void(brr&, int)> calc = [&](brr &pos, int now) {
if ((int)pos.size() == 1) {
std::cout << now << '\n';
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
std::cout << g[i][j] << ' ';
std::cout << '\n';
return;
}
brr p;
++now;
for (int i = 0; i < (int)pos.size(); i += k) {
p.emplace_back();
for (int j = i; j < i + k && j < (int)pos.size(); ++j) {
for (auto a : p.back())
for (auto b : pos[j])
g[a][b] = now;
for (auto b : pos[j])
p.back().push_back(b);
}
}
calc(p, now);
return;
};
calc(pos, 0);
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E - Edge Split
https://www.luogu.com.cn/problem/CF1726D
- 题意有些许歧义，『红色连通块』其实是指删掉蓝边之后的连通块。考虑到 \(m\le n+2\) 而不是更多，考虑直接分讨。
- 考虑树的情况，对于任意颜色，删一条边就会带来 \(1\) 个连通块的代价，随便染色即可。
考虑基环树的情况，发现如果环上有某个颜色，那么钦定这个颜色第一次删边删的是环边，就会发现第一次删边不会有代价，故强制环上有两种颜色即可。
考虑 \(m=n+1\) 的情况，环可能有下面三种形态：
对于第一、二种，保证两个环上都有两种颜色即可，第三种乍一看有点复杂，其实还是一样的，保证两个环都有两种颜色即可，这样三个环显然都会有两种颜色。站在不饱和度的角度，第三个环其实是无意义的。
由此类推 \(m=n+2\) 的情况，发现只需要在并查集连边时令树边为蓝，反祖边为红即可。发现这样会且仅会在第一组样例的情况出问题：
如果中间的三角形在最后输入就不能得到最优解 怎么处理这个问题呢，我们使用人类智慧，发现这种情况最后三条红边构成三角形，我们只要发现构造出来的解是这样的三角形，由于造成这一点的顺序很苛刻，故一直
random_shuffle输入，继续构造直到合法即可。（？怎么最优解全是这么做的，我还以为只有我一个人会乱搞。）
当不饱和度为 4 的时候就会出现这种结构：
此时按照刚刚的方法就一定构造不出合法解了。这或许也是 \(m\le n+2\) 的原因。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
std::mt19937 rand(0xabcdef);
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> res(m + 1);
std::vector<std::tuple<int, int, int> > e(m + 1);
for (int i = 1, x, y; i <= m; ++i) {
std::cin >> x >> y;
e[i] = { x, y, i };
}
auto work = [&](std::vector<std::tuple<int, int, int> > &e) {
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
std::set<int> t;
for (int i = 1; i <= m; ++i) {
auto [x, y, id] = e[i];
if (find(x) == find(y)) {
t.insert(x), t.insert(y);
res[id] = 1;
}
else {
res[id] = 0;
f[find(x)] = find(y);
}
}
return (int)t.size() != 3;
};
for (; !work(e); std::shuffle(e.begin() + 1, e.end(), rand));
for (int i = 1; i <= m; ++i)
std::cout << res[i];
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}F - Fair Share
https://www.luogu.com.cn/problem/CF1634E
原来 \(L=R\) 是说两个可重集相等 不是说和相等
考虑把所有元素排得整齐一点：同一组的在同一行，同一值的在同一列（显然这就要求每列元素个数为偶）。这样要求就转化为：分组，并满足每行每组各占一半、每列每组各占一半。
参考 Ball，用连边可以体现二选一的操作，发现其实二选一就是一选二分之一，故在行列中连边，按照 \((1,2)\)，\((3,4)\) 这样连边，就可以满足一选二分之一。
因为元素可重，所以一行一列可能会有多个元素，这不太好；实际实现时，不妨记输入的第 \(i\) 个数组第 \(j\) 个元素为 \(a_{i,j}\)，实际上连的是 \((a_{i,j},a_{i,j\oplus 1})\)；记值为 \(i\) 的第 \(j\) 个元素为 \(b_{i,j}\)，实际上连的是 \((b_{i,j},b_{i,j\oplus 1})\)。
还是参照 Ball 中二分图的观点，发现这个图很能二分图染色。如果这个解法是足够优的，我们当然希望不包含奇环。由于一个点在 \(a\) 中至多被连一条边，在 \(b\) 中也至多被连一条边，所以一条路径一定是 a b 交错的，由此证毕。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, tot = 0, N = 0;
std::cin >> n;
std::unordered_map<int, int> tab;
std::vector<std::vector<int> > a(n + 1), b(1);
for (int i = 1, m; i <= n; ++i) {
std::cin >> m;
for (int x; m--; ) {
std::cin >> x, ++N;
if (!tab.count(x))
tab[x] = ++tot, b.emplace_back();
a[i].push_back(N);
b[tab[x]].push_back(N);
}
}
std::vector<std::vector<int> > g(N + 1);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < (int)a[i].size(); ++j)
g[a[i][j]].push_back(a[i][j ^ 1]);
for (int i = 1; i <= tot; ++i) {
if ((int)b[i].size() & 1) {
std::cout << "NO\n";
return 0;
}
for (int j = 0; j < (int)b[i].size(); ++j)
g[b[i][j]].push_back(b[i][j ^ 1]);
}
std::cout << "YES\n";
std::vector<int> col(N + 1);
std::function<void(int, int)> DFS = [&](int x, int now) {
col[x] = now;
for (auto i : g[x])
if (!col[i])
DFS(i, 3 - now);
else
assert(col[i] != col[x]);
return;
};
for (int i = 1; i <= n; ++i) {
for (auto j : a[i]) {
if (!col[j])
DFS(j, 1);
std::cout << (col[j] == 1 ? 'L' : 'R');
}
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}G - Lenient Vertex Cover
https://www.luogu.com.cn/problem/CF1680F
对于边不被完全覆盖的限制把问题转换成了一个近似二分图染色的形态，一个朴素的做法是枚举这样的边并染色，但似乎没什么优化前途，考虑更加二分图的做法。
从非法的角度考虑，相当于是问能不能抠掉 \(\le 1\) 条边使图变为二分图。显然这条边（如果存在）在奇环上且是所有奇环的交。
从合法的角度考虑，因为不是真的删边，而是相当于把所在的所有环长度 \(-1\)，所以这条边不能被任何一个偶环包含。
容易想到找生成树，标记偶环边并统计奇环。但显然没办法标记到所有偶环边，也没办法统计到所有奇环：
实际上这个做法可以证明是正确的，因为有一个前提：非树边总是可以和树边成环。
考虑两个疑点：
无法标记到所有偶环：当且仅当存在偶环需要 \(\ge 2\) 条非树边参与形成。需要证明这样的偶环上的树边不会被选中。
单看这个环上的树边，形成 \(\ge 2\) 个条分立的链。考虑它们在树上是怎么连通的：
中间相隔奇数条树边。那么会被另一条非树边标记为偶环。
中间相隔偶数条树边。那么这两条链一定不会被认定为可选的奇环边，因为一条非树边 + 这偶数条边会形成一个新的、与当前偶环分立的奇环。
无法判定到所有奇环：当且仅当存在奇环需要 \(\ge 2\) 条非树边参与形成。需要证明被选中的边被包含在这样的奇环中。
相似地，单看这个环上的树边，形成 \(\ge 2\) 个条分立的链。考虑它们在树上是怎么连通的：
中间相隔偶数条树边。上帝视角下共两个奇环，且公共边为这个奇环中除了另一条非树边以外的所有边。
实际上的行为也是正确的，另一条非树边参与形成并标记一个偶环，当前非树边形成并标记一个奇环。
中间相隔奇数条树边。那么会被另一条非树边标记为偶环，当前奇环中唯一可选的边为当前非树边。
实际行为也是正确的。比较显然。
故树上差分维护即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int> > e;
std::vector<std::vector<int> > g(n + 1), g1(n + 1);
for (int i = 1, x, y; i <= m; ++i) {
std::cin >> x >> y;
e.emplace_back(x, y);
g1[x].push_back(y), g1[y].push_back(x);
}
std::vector<int> col(n + 1);
std::function<bool(int, int)> DFS = [&](int x, int now) {
col[x] = now;
for (auto i : g1[x])
if (!col[i]) {
if (!DFS(i, 3 - now))
return false;
}
else if (col[i] == now)
return false;
return true;
};
if (DFS(1, 1)) {
std::cout << "YES\n";
for (int i = 1; i <= n; ++i)
std::cout << col[i] - 1;
std::cout << '\n';
continue;
}
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::vector<std::pair<int, int> > r;
std::function<int(int)> find = [&](int x) { return x == f[x] ? x : f[x] = find(f[x]); };
for (auto [u, v] : e)
if (find(u) != find(v)) {
f[find(u)] = find(v);
// printf("%d %d \n", u, v);
g[u].push_back(v), g[v].push_back(u);
}
else
r.emplace_back(u, v);
std::vector<int> dep(n + 1), son(n + 1), siz(n + 1), fa(n + 1);
std::function<void(int)> DFS1 = [&](int x) {
siz[x] = 1;
for (auto i : g[x])
if (i != fa[x]) {
dep[i] = dep[x] + 1;
fa[i] = x, DFS1(i);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
dep[1] = 1, DFS1(1);
std::vector<int> top(n + 1);
DFS1 = [&](int x) {
if (son[x])
top[son[x]] = top[x], DFS1(son[x]);
for (auto i : g[x])
if (i != fa[x] && i != son[x])
top[i] = i, DFS1(i);
return;
};
top[1] = 1, DFS1(1);
auto askLCA = [&](int x, int y) {
for (; top[x] != top[y]; x = fa[top[x]])
if (dep[top[x]] < dep[top[y]])
std::swap(x, y);
return dep[x] < dep[y] ? x : y;
};
int cnt = 0;
std::pair<int, int> res;
std::vector<int> tag(n + 1), s(n + 1);
for (auto [u, v] : r) {
int fa = askLCA(u, v), dis = dep[u] + dep[v] - 2 * dep[fa];
if (dis & 1)
++tag[u], ++tag[v], tag[fa] -= 2;
else {
res = { 0, 0 };
++cnt, ++s[u], ++s[v], s[fa] -= 2;
if (cnt == 1)
res = { u, v };
}
}
DFS1 = [&](int x) {
for (auto i : g[x])
if (i != fa[x]) {
DFS1(i);
tag[x] += tag[i], s[x] += s[i];
}
if (!tag[x] && s[x] == cnt && x != 1)
res = { fa[x], x };
return;
};
DFS1(1);
// printf("# %d %d \n", res.first, res.second);
if (res.first) {
std::cout << "YES\n";
std::fill(col.begin() + 1, col.end(), 0);
std::function<void(int, int)> DFS = [&](int x, int now) {
col[x] = now;
for (auto i : g1[x])
if (!col[i])
DFS(i, 3 - now);
return;
};
col[res.first] = col[res.second] = 2;
DFS(res.first, 2), DFS(res.second, 2);
for (int i = 1; i <= n; ++i)
std::cout << col[i] - 1;
std::cout << '\n';
}
else
std::cout << "NO\n";
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}H - Four Coloring
https://www.luogu.com.cn/problem/AT_code_festival_2017_quala_d
参见切比雪夫距离，则问题转化为，任意点为中心的边长为 \(2d+1\) 的正方形的边不能和这个点同色
直接按照 \(d\times d\) 进行划分即可。注意负数除法会影响正确性，故平移到正数即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m, d;
std::cin >> n >> m >> d;
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j <= n + m; ++j) {
int x = (i + j) / d, y = (j - i) / d;
if (x % 2 == 0 && y % 2 == 0)
std::cout << 'R';
else if (x % 2 == 0)
std::cout << 'Y';
else if (y % 2 == 0)
std::cout << 'G';
else
std::cout << 'B';
}
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}I - Diverse Coloring
https://vjudge.net/contest/759882#problem/I
- 可以很简单地猜到答案为 \(n\bmod 2\)，且唯一的例外是样例中 \(n=4\) 的菊花；
很难理解怎么想到构造方法的：从根节点开始 DFS，先向下递归处理儿子，如果儿子传上来未配对的点则与之配对，否则上传自己。
这样做之后，除了根可能为孤岛之外，树会被分为若干个大小为 2 或 3 的连通块，此时的染色策略就很明显了。
1 的连通块的存在价值是保证每个点在包含其的连通块内都能解决掉限制，大小 \(=3\) 的连通块是为了提供 \(1\) 或 \(-1\) 的代价用于调整。
对于孤岛根，一个很好的性质是其儿子所在连通块一定是下面的两层，故大力讨论前三层形态（实际上是前五层）：
神秘枚举
分讨即可。似乎并不用分这么多类，但是实现难度并不高。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
std::vector<int> deg(n + 1);
std::vector<std::vector<int> > g(n + 1);
for (int i = 2, fa; i <= n; ++i) {
std::cin >> fa;
++deg[fa], ++deg[i];
g[fa].push_back(i);
if (i == 4 && *std::max_element(deg.begin() + 1, deg.begin() + 5) == 3)
std::cout << 2 << '\n';
else
std::cout << i % 2 << '\n';
}
std::vector<int> siz(n + 1);
std::vector<std::pair<int, int> > p2;
std::vector<std::tuple<int, int, int> > p3;
std::function<int(int)> DFS = [&](int x) {
std::vector<int> p;
p.push_back(x);
for (auto i : g[x])
if (DFS(i) == 1)
p.push_back(i);
if ((int)p.size() == 2)
p2.emplace_back(p[0], p[1]);
else if ((int)p.size() == 3)
p3.emplace_back(p[0], p[1], p[2]);
siz[x] = (int)p.size();
return siz[x];
};
std::vector<int> col(n + 1);
auto work = [&](int now) {
for (auto [x, y] : p2)
if (!col[x] && !col[y])
col[x] = 1;
for (auto [x, y, z] : p3)
if (!col[x] && !col[y] && !col[z]) {
if (now >= 0)
col[x] = 1, --now;
else
col[y] = col[z] = 1, ++now;
}
for (int i = 1; i <= n; ++i)
std::cout << (col[i] ? 'b' : 'w');
std::cout << '\n';
return;
};
DFS(1);
int now = 0;
if (siz[1] == 1) {
if ((int)g[1].size() == 1) {
int p2 = g[1][0];
if (siz[p2] == 2)
col[p2] = 1, now = -1;
else if (n == 4)
col[p2] = 1, now = -1;
else {
int p3 = g[g[p2][0]].empty() ? g[p2][1] : g[p2][0], p5 = g[p3][0];
col[p2] = col[p3] = 1;
if (siz[p5] == 2) {
int p6 = siz[g[p5][0]] == 1 ? g[p5][0] : g[p5][1];
col[p6] = 1, now = 0;
}
else {
int p6 = g[p5][0], p7 = g[p5][1];
col[p6] = col[p7] = 1, now = 1;
}
}
}
else {
int p2 = g[1][0], p3 = g[1][1];
if (siz[p2] > siz[p3])
std::swap(p2, p3);
if (siz[p2] == 2 && siz[p3] == 2)
col[p2] = col[p3] = 1, now = -1;
else if (siz[p2] == 2 && siz[p3] == 3) {
int p4 = siz[g[p2][0]] == 1 ? g[p2][0] : g[p2][1];
col[1] = col[p3] = col[p4] = 1, now = 0;
}
else {
int p4 = g[p2][0], p5 = g[p2][1];
col[1] = col[p3] = col[p4] = col[p5] = 1, now = 1;
}
}
}
work(now);
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}J - Graph Coloring
https://www.luogu.com.cn/problem/CF662B
首先需要意识到，翻奇数次 / 偶数次可以归到翻 / 不翻的范畴里。
不妨枚举最后所有边颜色，那么就可以限定每条边的两端点翻转情况，发现这是并查集，但怎么求最小？难道要 2-SAT 吗？
发现最终的并查集一定是两两对应的，对应每一对，取最小开销者即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::tuple<int, int, int> > e;
for (int i = 1, x, y; i <= m; ++i) {
char t;
std::cin >> x >> y >> t;
e.emplace_back(x, y, t == 'R');
}
std::vector<int> res1, res2;
auto calc = [&](std::vector<int> &res) {
std::vector<int> f(2 * n + 1), siz(2 * n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
f[find(x)] = find(y);
return;
};
for (auto [x, y, w] : e)
if (w)
merge(x, y), merge(x + n, y + n);
else
merge(x, y + n), merge(x + n, y);
for (int i = 1; i <= n; ++i) {
++siz[find(i)];
if (find(i) == find(n + i))
return false;
}
std::vector<int> tag(2 * n + 1);
for (int i = 1; i <= n; ++i) {
if (!tag[find(i)]) {
tag[find(i)] = tag[find(i + n)] = 1;
if (siz[find(i)] <= siz[find(i + n)])
++tag[find(i)];
else
++tag[find(i + n)];
}
if (tag[find(i)] == 2)
res.push_back(i);
}
return true;
};
auto flag1 = calc(res1);
for (auto &[x, y, w] : e)
w ^= 1;
auto flag2 = calc(res2);
if (!flag1 && !flag2)
std::cout << -1 << '\n';
else if (!flag2 || (flag1 && res1.size() < res2.size())) {
std::cout << (int)res1.size() << '\n';
for (auto i : res1)
std::cout << i << ' ';
std::cout << '\n';
}
else {
std::cout << (int)res2.size() << '\n';
for (auto i : res2)
std::cout << i << ' ';
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}