3495: PA2010 Riddle

链接

分析：

　　每个点要么建首都，要么不建，并且一个点建了，会导致一些点不能建。所以可以考虑2-sat。

　　但是如果在每个郡里两两连边，边数是n^2的。

　　考虑用前缀优化。

　　S[i]表示对于当前郡，前i个点中是否存在一个首都，A[i]表示i这个点是否建首都。

　　1、那么有A[i]=1,则S[i]=1，同样有它的逆否命题：S[i]=0,则A[i]=0。

　　2、根据前缀的性质有S[i-1]=1,则S[i]=1，逆否命题：S[i]=0,则S[i-1]=0。

　　3、由于每个郡只能有一个首都，所以A[i]=1,则S[i-1]=0，逆否命题：S[i-1]=1,则A[i]=0。

　　4、还有满足每条边两边至少一个首都，u=0,则v=1，逆否命题：v=0,则u=1

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

struct Edge{ int to, nxt; } e[N << ];

int head[N], dfn[N], low[N], bel[N], sk[N], top, Index, tot, En;

bool vis[N];

inline void add_edge(int u,int v) {

    ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;

}

void tarjan(int u) {

    low[u] = dfn[u] = ++Index;

    sk[++top] = u; vis[u] = ;

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (!dfn[v]) {

            tarjan(v);

            low[u] = min(low[u], low[v]);

        }

        if (vis[v]) low[u] = min(low[u], dfn[v]);

    }

    if (low[u] == dfn[u]) {

        ++tot;

        do {

            vis[sk[top]] = ;

            bel[sk[top]] = tot;

            top --;

        } while (sk[top + ] != u);

    }

}

int main() {

    int n = read(), m = read(), k = read();

    for (int u, v, i = ; i <= m; ++i) {

        u = read(), v = read();

        add_edge(u + n, v);add_edge(v + n, u);

    }

    for (int i = ; i <= n; ++i) // A[i]=1,S[i]=1

        add_edge(i, i +  * n), add_edge(i +  * n, i + n);

    for (int cnt, now, last, i = ; i <= k; ++i) {

        cnt = read(), last = read();

        for (int j = ; j <= cnt; ++j) {

            now = read();

            add_edge(last +  * n, now +  * n);add_edge(now +  * n, last +  * n); // S[i-1]=1,S[i]=1

            add_edge(now, last +  * n); add_edge(last +  * n, now + n); // A[i]=1,S[i-1]=0

            last = now;

        }

    }

    for (int i = ; i <= (n << ); ++i) if (!dfn[i]) tarjan(i);

    for (int i = ; i <= n; ++i) {

        if (bel[i] == bel[i + n] || bel[i +  * n] == bel[i +  * n]) {

            puts("NIE"); return ;

        }

    }

    puts("TAK");

    return ;

}