P13583 [NWRRC 2023] Colorful Village 题解

· · 题解

P13583 [NWRRC 2023] Colorful Village 题解

集训的课上出现了这道题，我听了思路觉得非常高妙。同样过的人不多，于是决定写题解，殊不知这是噩梦的开始……
WA 了28发，调+写七个小时，兜兜转转废寝忘食才终于写出这道题目。感慨万千。

Description

题意很简单：给定一个 2 \times n 个点的图，每个点有一种颜色，总共有 n 种颜色。要求给出一个颜色互不相同，且点数为 n 的联通块或者输出无解。

Solution

一样的，我们先观察样例。

发现一件事：模拟出这样一个联通块十分难以找到一个固定的策略！或许这是一个关键？启示我们可以先钦定一个根结点，然后考虑答案。

同时，一种颜色只有两个点，不多不少，而且有必须只选一个的限制。就像是把点分成了两部分！
略有所悟！建二分图吗？时间复杂度飞起来了！

继续思考：如果钦定了根结点且要求根结点必选，那么对于每一个点：只要我选了，我的父结点必须选上。否则联通块就断掉了。
两部分的点，而且点和点之间有选或不选的转移关系……

我们是不是可以把一种颜色看作一个布尔类型变量，选第一个点就是赋值为 0，选第二个点就是赋值为 1……

大彻大悟了！我们需要使用 2-SAT 解决这个问题！！

现在考虑怎么具体的建造 2-SAT 的。其他许多人的解法似乎都是对于每一个点建立选 / 不选的两条边，但是我觉得这样完全没有必要啊！
我们用 \neg p 表示与点 p 颜色相同的另一个点。每个颜色对应一个变量，由于每个变量一定会有赋值，联通块颜色不重复且大小为 n 的限制就自然而然被满足了！

接下来就只有一种不合法情况：我选了，我的父结点没有选。
以下条件满足其一即可：

构建形如 a \vee b 的若干组条件即可。

还有最后一个问题：如何选择钦定的根节点？有三种方式：

  1. 由于每次选择一半的点，随机选择根节点，选择 \log_2 n 次基本可以获得正确的构造。
  2. 一定有一个点颜色为 1 ，故分别选择颜色为 1 的两个结点当做根结点跑一遍即可。
  3. 因为树的重心子树的大小一定 \leq n ，所以答案一定包含树的重心，直接选择树的重心作为树根。

这里选择第二种写法。

code：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e6 + 10;
/*
各变量的含义：
T 数据组数
n ,l ,r ,thi_col 题目输入
cols 记录每个结点的颜色，第一次出现的颜色记为 i ，第二次记为 n+i
ctoi 通过颜色找到对应的结点
es ,es2 ,hd ,hd2 分别为输入的图和2-SAT建出的图
father 记录原图中的父子关系
is_can 这一组是否出现答案
tarjan 前面那一坨都是 tarjan 板子使用的
*/

ll n ,T;
ll cols[N] ,ctoi[N];
struct zxm {
    ll to ,nxt;
}es[N] ,es2[N];
ll hd[N] ,idx;
void add(ll u ,ll v) {
    es[++idx].to = v;
    es[idx].nxt = hd[u];
    hd[u] = idx;
}

ll hd2[N] ,iidx;
void add2(ll u ,ll v) {
    es2[++iidx].to = v;
    es2[iidx].nxt = hd2[u];
    hd2[u] = iidx;
}

ll is_can = 0 ,father[N];

void dfs(ll u ,ll fa) { //找父节点
    father[u] = fa;
    for (int i=hd[u] ;i ;i = es[i].nxt) {
        ll v = es[i].to;
        if (v == fa) {
            continue;
        }
        dfs(v ,u);
    }
}

ll dfn[N] ,low[N] ,idx_dfn ,st[N] ,top ,in_st[N];
ll bel[N] ,idx_b;
void tarjan(ll u) {
    dfn[u] = low[u] = ++idx_dfn;
    st[++top] = u;
    in_st[u] = 1;
    for (int i = hd2[u] ;i ;i = es2[i].nxt) {
        ll v = es2[i].to;
        if (dfn[v] == 0 ) {
            tarjan(v);
            low[u] = min(low[u] ,low[v]);
        }
        else if (in_st[v] == 1) {
            low[u] = min(low[u] ,dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ll thi = u;
        bel[thi] = ++idx_b;
        for (;;) {
            thi = st[top];
            top--;
            in_st[thi] = 0;
            bel[thi] = idx_b;
            if (thi == u) {
                break;
            }
        }
    }

}

void work (ll rt) { //跑2-SAT
    // init
    iidx = 0;
    for (int i=1 ;i<=2*n+2 ;i++) {
        hd2[i] = 0;
        father[i] = 0;
    }

    // 建新图
    dfs(ctoi[rt] ,0);
    for (int i=1 ;i<=n*2 ;i++) {
        if (father[i] == 0) { //我是电棍，我没有滚木
            continue;
        }
        ll anti_i ,anti_fa ,fa;
        fa = father[i];
        anti_i = ctoi[( (cols[i] > n) ? -1 : 1 ) * n + cols[i]];
        anti_fa = ctoi[( (cols[fa] > n) ? -1 : 1 ) * n + cols[fa]];
        //我没选 / 我爹选了 => choose anti_i or choose fa
        add2(i ,fa);
        add2(anti_fa ,anti_i);
    }

    //2-SAT part
    for (int i=1 ;i<=2*n+2 ;i++) {
        dfn[i] = low[i] = st[i] = in_st[i] = bel[i] = 0;
        idx_dfn = idx_b = top = 0;
    }

    for (int i=1 ;i<=n*2 ;i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    int flag = 1;
    for (int i=1 ;i<=n ;i++) {
        if (bel[ctoi[i]] == bel[ctoi[i+n]]) {
            flag = 0;
            break;
        }
    }
    if (flag == 0) {
        return;
    }
    is_can = 1;
    for (int i=1 ;i<=n ;i++) {
        if (bel[ctoi[i]] < bel[ctoi[i+n]]) {
            printf("%lld " ,ctoi[i]);
        }
        else {
            printf("%lld " ,ctoi[i+n]);
        }
    }
    printf("\n");
}

int main() {
    scanf("%lld" ,&T);
    for (;T--;) {
        //init
        idx = 0;
        is_can = 0;
        scanf("%lld" ,&n);
        for (int i=1 ;i<=2*n ;i++) {
            cols[i] = 0;
            ctoi[i] = 0;
        }

        for (int i=1 ;i<=2*n ;i++) {
            hd[i] = 0; // init
            ll thi_col;
            scanf("%lld" ,&thi_col);
            if (ctoi[thi_col] == 0) {
                cols[i] = thi_col;
                ctoi[thi_col] = i;
            }
            else {
                cols[i] = n + thi_col;
                ctoi[thi_col + n] = i;
            }
        }
        for (int i=1 ;i<2*n ;i++) {
            ll l ,r;
            scanf("%lld %lld" ,&l ,&r);
            add(l ,r);
            add(r ,l);
        }
        work(1);
        if (is_can == 1) {
            //cout<<"Sycamore_TY"<<endl;
            continue;
        } 
        work(1+n);
        if (is_can == 0) {
            printf("-1\n");
            continue; // 虽然不用写这一行但是仪式感这一块
        }
    }
    return 0;
}

有关为什么我写了七个小时，可以观看我发的帖子。。。