P4782 题解

神眷之樱花 · 2021-05-02 22:04:46 · 题解

博客阅读更佳

My Blog

题解

连边

• 定义点 x 表示(x-(x>n)*n)=(x>n)，也就是：
• 如果点 x\leq n，则代表第 x 个数为 0。
• 如果点 x\geq n+1，则代表第 x-n 个数为 1。
• 定义边 (x,y) 由 (x-(x>n)*n)=(x>n) 可以推出 (y-(y>n)*n)=(y>n)。

对于条件 (x=a||y=b)，我们可以转化为：

由此我们就知道了该怎么连边。

add(x + (a ^ 1) * n,y + b * n);
add(y + (b ^ 1) * n,x + a * n);

判无解

于是连完后，我们跑一遍tarjan，求出其中的强连通分量，如果 x 和 x+n 同处于一个强连通分量内，那么显然无解。原因很显然，这意味着我们从 x=0 推出了 x = 1。

构造值

接下来是构造值的问题。 我用的是小蓝书的第二种方法，这里就不赘述原理了。

代码

#include<cstdio>
#include<iostream>
using std::min;
const int N = 2e6 + 5;
struct edge {
    int next,to;
}a[N << 1];
int head[N],opp[N],n,m,a_size = 1;
inline void add(int u,int v) {
    a[++a_size] = (edge){head[u],v};
    head[u] = a_size;
}
int dfn[N],low[N],sta[N],c[N],top = 0,cnt = 0,num = 0;
bool ins[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    sta[++top] = x; ins[x] = true;
    for(int i = head[x]; i; i = a[i].next) {
        int y = a[i].to;
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }
        else if(ins[y])
            low[x] = min(low[x],dfn[y]); 
    }
    if(dfn[x] == low[x]) {
        int y; cnt++;
        do {
            y = sta[top--]; ins[y] = false;
            c[y] = cnt;
        }while(x != y);
    }
}
inline int read() {
    int x = 0,flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')flag = -1;ch = getchar();}
    while(ch >='0' && ch <='9'){x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}
    return x * flag;
}
int main() {
    n = read(),m = read();
    for(int i = 1; i <= m; i++) {
        int x = read(),a = read(),y = read(),b = read();
        add(x + (a ^ 1) * n,y + b * n);
        add(y + (b ^ 1) * n,x + a * n);
    } n <<= 1;
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);
    n >>= 1;
    for(int i = 1; i <= n; i++)
        if(c[i] == c[i + n]) {puts("IMPOSSIBLE"); return 0;}
    puts("POSSIBLE");
    for(int i = 1; i <= n; i++)
        printf("%d ",c[i] > c[n + i]);
    return 0;
}