[洛谷P4171]满汉全席题解

~~我饿了~~（误

传送门

~~反手切一道紫题，闷声发大财~~

不开玩笑了

题意

有 $n$ 种材料， $m$ 个要求，其中每个要求中的两个小要求 ~~（好绕啊~~ 必须满足至少一个（也就是或）

思路

不难看出，对于每种材料只有两种可能，即满式和汉式

因此，这题可以用2-SAT!

不懂的可以来我的这篇博客学习

~~然后就是考你模板背的熟不熟了~~

对了

输入要注意一下

快读党可能得微调一下读入的函数

其它就没啥了

上代码

标程

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;

//链式前向星，不想解释
struct edge{
    int to,next;
}e[N<<1];
int last[N],cnt;
//建边操作
void add_edge(int x,int y){
    cnt++;
    e[cnt].next=last[x];
    e[cnt].to=y;
    last[x]=cnt;
}

int n,m,x,y;
char c1,c2;

//Tarjan模板
int dfn[N],low[N],scc[N],dcnt,icnt;
stack<int> st;
void tarjan(int x){
    st.push(x);
    dfn[x]=low[x]=++dcnt;
    for(int i=last[x];i;i=e[i].next){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(!scc[y]){
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]){
        icnt++;
        while(st.top()!=x){
            scc[st.top()]=icnt;
            st.pop();
        }
        scc[st.top()]=icnt;
        st.pop();
    }
}

int main(){
    int k;
    scanf("%d\n",&k);
    //多组数据
    while(k--){
        scanf("%d %d\n",&n,&m);
        //建边前初始化
        memset(last,0,sizeof(last));cnt=0;
        //1-n表示满式做法，n+1-2*n为汉式做法
        for(int i=1;i<=m;i++){
            //用scanf格式化输入就是香…
            scanf("%c%d %c%d\n",&c1,&x,&c2,&y);
            if(c1=='m'&&c2=='m'){
                //一个是汉式，另一个就要是满式
                add_edge(x+n,y);add_edge(y+n,x);
            }
            else if(c1=='m'&&c2=='h'){
                //1为汉式，2就要为汉式；反之亦然
                add_edge(x+n,y+n);add_edge(y,x);
            }
            else if(c1=='h'&&c2=='m'){
                //同上
                add_edge(x,y);add_edge(y+n,x+n);
            }
            else{
                //一个是满式，则另一个为汉式
                add_edge(y,x+n);add_edge(x,y+n);
            }
        }
        //缩点前初始化
        memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(scc,0,sizeof(scc));
        //图不一定连通…注意
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        int flag=0;
        for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) {flag=1;break;}
        if(!flag) printf("GOOD\n");
        else printf("BAD\n");
    }
    return 0;
}