【题解】BZOJ 3495 [PA2010]Riddle

Problem

有 $n$ 个城镇被分成了 $k$ 个郡,有 $m$ 条连接城镇的无向边
要求给每个郡选择一个城镇作为首都,满足每条边至少有一个端点是首都

Thought

对于每一条边来说,限制两边至少选一个,也就是 $x_i\lor x_j=1$
对于每一个郡来说,限制最多选一个,也就是 $x_i\land x_j=0$

将其转化为 $2-SAT$ 模型就完事了

但是由于一个郡会有 $n^2$ 条连边,这样就很麻烦

考虑对每一个郡新建 $2siz$ 个点,分别表示前 $i$ 个是否被选和后 $i$ 个是否被选

表示前 $i$ 个点被选的点将连向表示正数第 $i+1$ 个点不选的节点以及表示前 $i+1$ 个点被选的点
表示后 $i$ 个点被选的点将连向表示倒数第 $i+1$ 个点不选的节点以及表示后 $i+1$ 个点被选的点

然后 $Tarjan$ $SCC$ 完事

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 1000010;

struct Edge {
    int t, n;
}e[N << 3];
int head[N << 2], Etot;

void addedge(int u, int v) {
    e[++ Etot] = {v, head[u]};
    head[u] = Etot;
}
int n, m, k;
int a[N];


int dfn[N << 2], low[N << 2], DFN;
int sta[N << 2], top;
bool vis[N << 2];
int id[N << 2], cnt;
void dfs(int x) {
    dfn[x] = low[x] = ++ DFN;
    sta[++ top] = x; vis[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        int t = e[i].t;
        if(!dfn[t]) {
            dfs(t);
            low[x] = min(low[x], low[t]);
        }
        else if(vis[t])
            low[x] = min(low[x], dfn[t]);
    }
    if(low[x] == dfn[x]) {
        ++ cnt;
        while(sta[top] != x) {
            id[sta[top]] = cnt;
            vis[sta[top]] = 0;
            sta[top --] = 0;
        }
        id[sta[top]] = cnt;
        vis[sta[top]] = 0;
        sta[top --] = 0;
    }
}

int main() {
    n = read(); m = read(); k = read();
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        addedge(2 * n + v, u);
        addedge(2 * n + u, v);
    }
    int sizSum = n;
    for(int i = 1; i <= k; ++ i) {
        int siz = read();
        for(int j = 1; j <= siz; ++ j)
            a[j] = read();
        for(int j = 1; j < siz; ++ j) {
            addedge(a[j], sizSum + j);
            addedge(sizSum + j, 2 * n + a[j + 1]);
            addedge(sizSum + j, sizSum + j + 1);
        }
        for(int j = siz; j > 1; -- j) {
            addedge(a[j], 2 * n + sizSum + j);
            addedge(2 * n + sizSum + j, 2 * n + a[j - 1]);
            addedge(2 * n + sizSum + j, 2 * n + sizSum + j - 1);
        }
        sizSum += siz;
    }
    for(int i = 1; i <= (n << 2); ++ i)
        if(!dfn[i])
            dfs(i);
    for(int i = 1; i <= n; ++ i)
        if(id[i] == id[2 * n + i]) {
            puts("NIE");
            return 0;
        }
    puts("TAK");
    return 0;
}
Comments

添加新评论