CF662B 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 ，逃过一劫。