洛谷P4171/JSOI2010 满汉全席

@Pelom  November 1, 2019

题意

数据范围:$n \le 100,m \le 1000$

题解

容易想到这是一个$\text{2-SAT}$问题
将每种材料拆成满/汉两种选择,分别为$i,i+n$,每个评审的要求可以看作“或”
建图跑$\text{Tarjan}$,判断$i,i+n$是否在同一强连通分量里

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100+10;
const int M=1000+10;
int t,n,m,u,v;
char c1,c2;
int cnt,top,dep,tot;
int head[N<<1],dfn[N<<1],low[N<<1],stk[N<<1],clr[N<<1];
struct edge{
    int nxt,to;
} e[M<<1];
inline void read(char& op,int& x){
    x=0;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c=='m' || c=='h')
            op=c;
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
}
inline void add(int u,int v){
    e[++cnt]=edge{head[u],v};
    head[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++dep;
    stk[++top]=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]);
        }
        else if(!clr[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        tot++;
        for(int t=0;t!=u;){
            t=stk[top--];
            clr[t]=tot;
        }
    }
}
inline bool check(){
    for(int i=1;i<=n;i++)
        if(clr[i]==clr[i+n])
            return 0;
    return 1;
}
int main(){
    scanf("%d",&t);
    for(;t--;){
        cnt=top=dep=tot=0;
        memset(head,0,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(clr,0,sizeof(clr));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            read(c1,u);
            read(c2,v);
            if(c1=='m')
                if(c2=='m'){
                    add(u+n,v);
                    add(v+n,u);
                }
                else{
                    add(u+n,v+n);
                    add(v,u);
                }
            else
                if(c2=='m'){
                    add(u,v);
                    add(v+n,u+n);
                }
                else{
                    add(u,v+n);
                    add(v,u+n);
                }
        }
        for(int i=1;i<=(n<<1);i++)
            if(!dfn[i])
                Tarjan(i);
        if(check())
            puts("GOOD");
        else puts("BAD");
    }
    return 0;
}

添加新评论