BZOJ1823：[JSOI2010]满汉全席——题解

水深无声 2021-09-20 11:46 255阅读 0赞

[https://www.lydsy.com/JudgeOnline/problem.php?id=1823][https_www.lydsy.com_JudgeOnline_problem.php_id_1823]

[https://www.luogu.org/problemnew/show/P4171][https_www.luogu.org_problemnew_show_P4171]

题面太长啦就不粘过来啦！

裸的2-SAT用来练板子的。

显然属于“a和b之间必须选一种”模型，只要a'向b连边，b'向a连边即可。

（被这题读入坑了orz）

#include<cstdio>
    #include<queue>
    #include<cctype>
    #include<cstring>
    #include<cmath>
    #include<stack>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int N=1005;
    const int M=20005;
    struct node{
        int to,nxt;
    }e[M];
    int T,n,m,head[N],cnt;
    int dfn[N],low[N],t,l;
    int to[N];
    bool inq[N];
    stack<int>q;
    inline int neg(int x){
        if(x>n)return x-n;
        return x+n;
    }
    inline void add(int u,int v){
        e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
    }
    void tarjan(int u){
        dfn[u]=low[u]=++t;
        q.push(u);inq[u]=1;
        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]);
            }else if(inq[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(dfn[u]==low[u]){
            int v;l++;
            do{
                v=q.top();q.pop();
                inq[v]=0;to[v]=l;
            }while(u!=v);
        }
    }
    inline void init(){
        cnt=t=l=0;
        memset(head,0,sizeof(head));
        memset(dfn,0,sizeof(dfn));
    }
    inline int get(){
        int k;char ch=0;
        while(ch!='m'&&ch!='h')ch=getchar();
        scanf("%d",&k);
        if(ch=='h')k+=n;
        return k;
    }
    int main(){
        scanf("%d",&T);
        while(T--){
            init();
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++){
                int a=get(),b=get();
                add(neg(a),b);
                add(neg(b),a);
            }
            for(int i=1;i<=2*n;i++)
                if(!dfn[i])tarjan(i);
            bool flag=1;
            for(int i=1;i<=n&&flag;i++){
                if(to[i]==to[i+n])flag=0;
            }
            if(flag)puts("GOOD");
            else puts("BAD");
        }
    }

\+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：[http://www.cnblogs.com/luyouqi233/][http_www.cnblogs.com_luyouqi233]\+

\+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/9022107.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_1823]: https://www.lydsy.com/JudgeOnline/problem.php?id=1823
[https_www.luogu.org_problemnew_show_P4171]: https://www.luogu.org/problemnew/show/P4171
[http_www.cnblogs.com_luyouqi233]: http://www.cnblogs.com/luyouqi233/