[JSOI2010]满汉全席 2-SAT

https://www.luogu.org/problemnew/show/P4171

意识到图中只有两种不同的菜系：满和汉

并且检查员类似于一个约束，可以发现这就是一个2-sat模型，满和汉分别对应true和false

由于只是检查可行性，只需要判断存在点的true个false存在同一个强连通分量即可。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

int read(){int x = ,f = ;char c = getchar();while (c<'' || c>''){if (c == '-') f = -;c = getchar();}

while (c >= ''&&c <= ''){x = x *  + c - '';c = getchar();}return x*f;}

const double eps = 1e-;

const int maxn = ;

const int maxm = ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

struct Edge{

    int to,next;

}edge[maxm << ];

int head[maxn],tot;

int Low[maxn],dfn[maxn],Stack[maxn],Belong[maxn];

int Index,top,scc;

bool Instack[maxn];

void init(){

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

        head[i] = -;

        Low[i] = dfn[i] = Belong[i] = Instack[i] = ;

    }

    tot = scc = top = Index = ;

}

void add(int u,int v){

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void Tarjan(int u){

    int v;

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

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u]; ~i ; i = edge[i].next){

        v = edge[i].to;

        if(!dfn[v]){

            Tarjan(v);

            if(Low[u] > Low[v]) Low[u] = Low[v];

        }else if(Instack[v] && Low[u] > dfn[v]) Low[u] = dfn[v];

    }

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

        scc++;

        do{

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = scc;

        }while(v != u);

    }

}

int main(){

//    ios::sync_with_stdio(false);

    int T = read();

    while(T--){

        cin >> N >> M; init();

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

            char op1,op2; int x,y;

            cin >> op1 >> x >> op2 >> y;

            int flag1 = op1 == 'm'?:;

            int flag2 = op2 == 'm'?:;

            add(x + N * (flag1 ^ ),y + N * (flag2 & ));

            add(y + N * (flag2 ^ ),x + N * (flag1 & ));

        }

        for(int i = ; i <= (N << ) ; i ++) if(!dfn[i]) Tarjan(i);

        int flag = ;

        for(int i = ; i <= N && flag; i ++){

            if(Belong[i] == Belong[i + N]) flag = ;

        }

        if(flag) puts("GOOD");

        else puts("BAD");

    }

    return ;

}

秒客网

[JSOI2010]满汉全席 2-SAT

相关文章