LUOGU P4171 [JSOI2010]满汉全席

解题思路

2-SAT 裸题。
代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int MAXN = 1005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?-1:1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,m,T,head[MAXN],cnt,col_num,num;

int to[MAXN<<1],nxt[MAXN<<1],bl[MAXN];

int stk[MAXN],top,low[MAXN],dfn[MAXN];

bool vis[MAXN];

inline void add(int bg,int ed){

    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void tarjan(int x){

    low[x]=dfn[x]=++num;vis[x]=1;stk[++top]=x;

    for(register int i=head[x];i;i=nxt[i]){

        int u=to[i];

        if(!dfn[u]) {

            tarjan(u);

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

        }

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

    }

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

        vis[x]=0;bl[x]=++col_num;

        while(stk[top]!=x){

            vis[stk[top]]=0;

            bl[stk[top--]]=col_num;

        }top--;

    }

}

int main(){

    T=rd();char c1[10],c2[10];

    while(T--){

        memset(head,0,sizeof(head));

        memset(bl,0,sizeof(bl));

        memset(dfn,0,sizeof(dfn));

        memset(low,0,sizeof(low));

        memset(nxt,0,sizeof(nxt));

        memset(to,0,sizeof(to));

        top=num=col_num=cnt=0;

        n=rd();m=rd();bool flag=false;

        for(register int i=1;i<=m;i++){

            scanf("%s%s",c1+1,c2+1);

            int sx=0,sy=0,tx=0,ty=0,x=0,y=0,t1=2,t2=2;

            if(c1[1]=='m') sx=1;if(c2[1]=='m') sy=1;

            tx=sx^1,ty=sy^1;

            while(isdigit(c1[t1])) x=(x<<1)+(x<<3)+c1[t1++]-'0';

            while(isdigit(c2[t2])) y=(y<<1)+(y<<3)+c2[t2++]-'0';

//          cout<<x<<" "<<y<<endl;

            add(x<<1|tx,y<<1|sy);add(y<<1|ty,x<<1|sx);

        }

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

        for(register int i=1;i<=n;i++)

            if(bl[i<<1]==bl[i<<1|1]) {

                puts("BAD");flag=1;

                break;

            }

        if(!flag) puts("GOOD");

    }

    return 0;

}
巴特西

LUOGU P4171 [JSOI2010]满汉全席

解题思路

代码

最新文章

热门文章
