题解 CF1215F 【Radio Stations】

Sooke · 2019-09-16 11:45:20 · 题解

简要题意

有 n 个电台，第 i 个电台频段在 [l_i,\,r_i] 。由你在 [1,\,m] 中选择主频 f ，如果 f \in [l_i,\,r_i] ，第 i 个电台你可选择是否启用，否则无法启用。

有若干组限制形如 u 和 v 必须启用至少一个，或不可同时启用。请给出 f 并构造电台的启用方案。无解输出 -1 。

前置知识

--- ### 解题思路按照 $\text{2 - SAT}$ 的套路，我们把一个对象拆成两个点分别表示选和不选。于是我们掏出 $2n$ 个点，来描述 $n$ 个电台的启用方案。但最重要的考点，还是建模。下文用 $\text{yes}(u)$ 表示表示对象 $u$ 选的点，$\text{no}(u)$ 表示对象 $u$ 不选的点。首先来热一热身，“若干组限制形如电台 $u$ 和电台 $v$ 必须启用至少一个”怎么在 $\text{2 - SAT}$ 中表示呢？回忆一下，既然点表示选或不选，那么条件 $u$ 往条件 $v$ 连一条有向边表示只要条件 $u$ 满足，条件 $v$ 就必须满足。因此，我们只要像下面一样连边： ![](https://i.loli.net/2019/09/16/6wek2Vd3sMmDFJH.png) 即：$\text{no}(u) \rightarrow \text{yes}(v),\ \text{no}(v) \rightarrow \text{yes}(u)$ 。理由很简单。当 $u$ 不选时，如果 $v$ 还不选的话，就不满足限制了，这意味着 $v$ 不得不选。反过来亦然。下一个热身任务：若干组限制形如电台 $u$ 和电台 $v$ 不可同时启用。连边方式异曲同工： ![](https://i.loli.net/2019/09/16/vR9NFuSekpByOAd.png) 即：$\text{yes}(u) \rightarrow \text{no}(v),\ \text{yes}(v) \rightarrow \text{no}(u)$ 。理由也类似。当 $u$ 选，$v$ 必须不能选，否则违反限制。反过来亦然。热身结束。真正振奋人心的建模这才到来：如何制定唯一的 $f$ ，并表示出因为 $f \notin [l_i,\,r_i]$ ，$i$ 号电台不允许启用？线段树优化建边？太慢！太繁琐！我们需要**前缀和的思想**！试试把区间 $[l,\,r]$ 拆成 $[1,\,l-1]$ 和 $[1,\,r]$ 来讨论。列出以下表格： |||| |:-:|:-:|:-:| |$\quad f\in [1,\,l_i - 1]\quad $|$\quad f\in [1,\,r_i]\quad $|$\quad $电台 $i$ 能否启用$\quad $| |$\text{no}$|$\text{no}$|$\text{no}$ ，此时 $f > r_i$| |$\text{no}$|$\text{yes}$|没有限制，此时 $f \in [l_i,\,r_i]$| |$\text{yes}$|$\text{yes}$|$\text{no}$ ，此时 $f < l_i$| |$\text{yes}$|$\text{no}$|不存在，$f \in \varnothing$| 据此，提取出三个重要限制： - 若电台 $i$ 启用，$f \in [l_i,\,r_i]$ 。 - 若 $f \in [1,\,l_i-1]$ 满足，电台 $i$ 无法启用。 - 若 $f \in [1,\,r_i]$ 不满足，电台 $i$ 无法启用。与此同时，我们发现仅凭目前的 $2n$ 个点，不足以表示出上面的限制。于是我们再掏出 $2(m+1)$ 个点，分别表示对于 $i = 0 \dots m$ ，$[f \le i]$ 满足或不满足。例如，用 $\text{yes}(n + i + 1)$ 表示 $f \le i$ ，用 $\text{no}(n + i + 1)$ 表示 $f > i$ 。它们之间的连边如下： ![](https://i.loli.net/2019/09/16/b4kYHJQa1t2938n.png) 即：$\text{yes}(n+i+1) \rightarrow \text{yes}(n+i+2),\ \text{no}(n+i+2) \rightarrow \text{no}(n+i+1)$ 。解释：$f \le i$ 满足时，$f \le i + 1$ 必然满足。$f \le i + 1$ 不满足时，即 $f \ge i + 1$ 满足时，$f \le i$ 必然不满足。至此，我们终于准备在两类对象之间连边了！复读一遍那三个限制： - 若电台 $i$ 启用，$f \in [l_i,\,r_i]$ 。 - 若 $f \in [1,\,l_i-1]$ 满足，电台 $i$ 无法启用。 - 若 $f \in [1,\,r_i]$ 不满足，电台 $i$ 无法启用。转换成连边关系就是： - $\text{yes}(i) \rightarrow \text{no}(n+l_i),\ \text{yes}(i) \rightarrow \text{yes}(n+r_i+1)

\text{yes}(n+l_i) \rightarrow \text{no}(i)
\text{no}(n+r_i+1) \rightarrow \text{no}(i)

还有一个小细节，f 不能等于 0 ！有个巧妙的连边是 \text{yes}(n+1) \rightarrow \text{no}(n+1) ，这样 \text{yes}(n+1) 成立时会造成矛盾，\text{no}(n+1) 成立时刚好不会有问题。

建完图后，跑一跑 \text{2 - SAT} 就行啦！判断无解的方法跟模板题一样，而有解时的 f ，满足 \text{yes}(n+f+1) ，\text{no}(n+f) 成立，跑完 \text{2 - SAT} 后枚举找到这个分界点即可。

代码实现

注意我的代码实现里 n 个电台是从 0 到 n - 1 标号的。

#include <bits/stdc++.h>

inline int read() {
    char c; int x; for (c = getchar(); !isdigit(c); c = getchar());
    for (x = 0; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } return x;
}

const int N = 2e6 + 5, E = 4e6 + 5;

struct List {
    int tot, fst[N], nxt[E], to[E];

    List() { memset(fst, -1, sizeof(fst)); }
    inline void insert(int u, int v) {
        nxt[tot] = fst[u]; to[tot] = v; fst[u] = tot++;
    }
    inline void link(int u, int v) {
        insert(u, v); insert(v ^ 1, u ^ 1);
    }
} e;

int n, m, m0, m1, k, c, tms, vol, dfn[N], low[N], stc[N], col[N];
bool ins[N];

inline int yes(int u) { return u << 1; }
inline int no(int u) { return u << 1 | 1; }

void tarjan(int u) {
    dfn[u] = low[u] = tms++;
    int pos = vol; stc[vol++] = u; ins[u] = true;
    for (int i = e.fst[u]; ~i; i = e.nxt[i]) {
        int v = e.to[i];
        if (dfn[v] == -1) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (ins[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        while (vol > pos) {
            int v = stc[--vol];
            col[v] = c; ins[v] = false;
        } c++;
    }
}

bool solve() {
    for (int i = 0; i <= no(n + m); i++) { dfn[i] = -1; }
    for (int i = 0; i <= no(n + m); i++) {
        if (dfn[i] == -1) { tarjan(i); }
    }
    for (int i = 0; i <= n + m; i++) {
        if (col[yes(i)] == col[no(i)]) { return false; }
    } return true;
}

int main() {
    m0 = read(); n = read(); m = read(); m1 = read();
    for (int i = 0; i < m0; i++) {
        int u = read(), v = read(); u--; v--;
        e.link(no(u), yes(v));
    }
    for (int i = 0; i < m; i++) {
        e.link(yes(n + i), yes(n + i + 1));
    } e.link(yes(n), no(n));
    for (int i = 0; i < n; i++) {
        int l = read(), r = read();
        e.link(yes(i), no(n + l - 1));
        e.link(yes(i), yes(n + r));
    }
    for (int i = 0; i < m1; i++) {
        int u = read(), v = read(); u--; v--;
        e.link(yes(u), no(v));
    }
    if (solve()) {
        for (int i = 0; i < n; i++) {
            if (col[yes(i)] < col[no(i)]) { k++; }
        }
        for (int i = 1; i <= m; i++) {
            if (col[yes(n + i)] < col[no(n + i)]) {
                printf("%d %d\n", k, i); break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (col[yes(i)] < col[no(i)]) { printf("%d ", i + 1); }
        }
    } else {
        puts("-1");
    }
    return 0;
}