P4171 [JSOI2010]满汉全席

简要的学了一下2-sat，然而不会输出方案。
就是个sb模板题啦
// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int fir[201],dis[2010],nxt[2010],id,dfn[201],low[201],stk[201],top,ins[201],scc[201];

il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}

char a[10],b[10];

il vd tarjan(int x){

    dfn[x]=low[x]=++dfn[0];stk[++top]=x;ins[x]=1;

    for(int i=fir[x];i;i=nxt[i])

        if(!dfn[dis[i]])tarjan(dis[i]),low[x]=std::min(low[x],low[dis[i]]);

        else if(ins[dis[i]])low[x]=std::min(low[x],dfn[dis[i]]);

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

        ++scc[0];

        while(stk[top+1]!=x)ins[stk[top]]=0,scc[stk[top]]=scc[0],--top;

    }

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("4171.in","r",stdin);

    freopen("4171.out","w",stdout);

#endif

    int n,m,T=gi();

    while(T--){

        n=gi(),m=gi();

        memset(fir,0,sizeof fir);id=0;

        memset(stk,0,sizeof stk);

        memset(dfn,0,sizeof dfn);

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

            scanf("%s%s",a,b);

            if(a[0]=='h')std::swap(a,b);

            int A=atof(a+1),B=atof(b+1);

            if(a[0]=='h')link(A+n,B),link(B+n,A);

            else if(b[0]!='m')link(A,B),link(B+n,A+n);

            else link(A,B+n),link(B,A+n);

        }

        scc[0]=0;

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

        for(int i=1;i<=n;++i)if(scc[i]==scc[i+n]){puts("BAD");goto GG;}

        puts("GOOD");

      GG:;

    }

    return 0;

}
巴特西

P4171 [JSOI2010]满汉全席

最新文章

热门文章
