CF662B Graph Coloring 题解
题目链接：Graph Coloring
题意：
给出一张 \(n\) 个点，\(m\) 条边的无向图，一开始每条边可能是红色或者蓝色，
翻转一个点可以使相连的边变成相反的颜色，要求把所有边变成红色或者蓝色
问最少需要翻转的点数，并给出具体的方案
输入格式：
第一行输入 \(n,m\)，分别表示点的数量和边的数量 \((1\leq n,m\leq 100000)\) 。
第二至 \(m+1\) 行 \(u_i,v_i,c_i\)，分别表示无向边的两个点以及它的颜色，保证没有重边和自环
输出格式：
如果没有方法使其合法输出 \(-1\)，
否则第一行输出最少需要翻转的点数，第二行用空格分隔输出翻转点的编号，只需要输出一种方案
考虑对全部染成 \(\mathbf{R}\) 和全部染成 \(\mathbf{B}\) 的方案取 min。
下面以 \(\mathbf{R}\) 为例。显然每个点至多翻转 \(1\) 次，那么记 \(i\) 为点 \(i\) 不翻转，\(i + n\) 为点 \(i\) 翻转。
- 若 \(c_i = \mathbf{R}\) ，连双向边 \((u_i,v_i)\) 和 \((u_i + n,\,v_i + n)\) ，即要么同时翻转，要么同时不翻转。
- 否则，连双向边 \((u_i,\,v_i + n)\) 和 \((u_i + n,\,v_i)\) ，即翻转一个的话，另一个就不能翻转。
直接跑 2–SAT，如果 \(i\) 和 \(i + n\) 在一个 SCC（强连通分量）内则无解。
由于本题连的都是双向边，所以选点 \(i\) 就必须选整个 SCC。
那么对于 \(i\) 和 \(i+n\) 所在的两个 SCC ，我们只需要贪心地选择点数少的那个即可
因为每个 \(i\) 都在 SCC 中，所以这么选一定是最优的。当然这题也可以并查集，都是双向边嘛。
时间复杂度 \(\mathcal{O}(n + m)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(2e5 + 15))
int n;
struct Graph
{
vector<int> ans, vec[N], id[N]; bool ins[N], vis[N];
int res, tim, scnt, stktop, stk[N], dfn[N], low[N], top[N], scc[N];
void add2(int u, int v) { vec[u].pb(v); vec[v].pb(u); }
void Tarjan(int u)
{
dfn[u] = low[u] = ++tim; ins[stk[++stktop] = u] = true;
for(auto v : vec[u])
{
if(!dfn[v]) { Tarjan(v); down(low[u], low[v]); }
else if(ins[v]) down(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
top[++scnt] = u;
for(int p = 0; p != u; )
{
p = stk[stktop--];
ins[p] = false; scc[p] = scnt;
if(p > n) id[scnt].pb(p - n);
}
}
}
void solve()
{
rep(i, 1, 2 * n) if(!dfn[i]) Tarjan(i);
rep(i, 1, n) if(scc[i] == scc[i + n]) { return res = INF, void(); }
rep(i, 1, n) if(!vis[scc[i]])
{
vis[scc[i]] = vis[scc[i + n]] = true;
if(id[scc[i]].size() < id[scc[i + n]].size())
{
auto &v = id[scc[i]]; res += (int)v.size();
ans.insert(ans.end(), v.begin(), v.end());
}else
{
auto &v = id[scc[i + n]]; res += (int)v.size();
ans.insert(ans.end(), v.begin(), v.end());
}
}
}
} G[2];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int m, x, y; bool z; char c; cin >> n >> m;
rep(i, 1, m)
{
cin >> x >> y >> c; z = (c == 'B');
G[z].add2(x, y); G[z].add2(x + n, y + n);
G[!z].add2(x, y + n); G[!z].add2(x + n, y);
}
G[0].solve(); G[1].solve();
bool k = (G[0].res > G[1].res);
if(G[k].res == INF) return cout << "-1\n", 0;
cout << G[k].res << '\n';
rep(i, 0, (int)G[k].ans.size() - 1)
cout << G[k].ans[i] << " \n"[i == iEND];
return 0;
}然后这里最后第四行有个超级无敌大坑！！！为此我还发了一个讨论，感谢评论区那位巨佬。
如果把那个 (int) 去掉，交上去会发现除了 C++20 都会
Runtime error on test 36 。
因为我习惯 #define int long long
，所以这句话翻译出来应该是：
for(long long i = 0, iEND = G[k].ans.size() - 1; i <= iEND; i++)
cout << G[k].ans[i] << " \n"[i == iEND];注意到这里 G[k].ans.size() 它的类型是
size_t ，这个东西取决于机器是 32 位还是 64 位
然后 CodeForces 上除了 Cpp20 是 64 位机器，其他都是 32 位机器。
对于 32 位机器，这里 size_t 的类型是
unsigned int，则
G[k].ans为空时，(i32u)0-1==(i64)I32U_MAX，出问题了对于 64 位机器，这里 size_t 的类型是
unsigned long long，则
G[k].ans为空时，(i64u)0-1==(i64)I64U_MAX==-1，逃过一劫。
这就导致我之前一直挂，找了半天都找不到原因。
因此各位，以后碰到 size_t 一定要转成 int
啊！！！！！
参考文献：
