[JSOI2010] 满汉全席

Author Avatar
空気浮遊 2018年03月17日
  • 在其它设备中阅读本文章

Problem

一种材料可以做成满式和汉式。
每个厨师想吃两道菜,可能是某个材料做成的某道菜式。
只要满足厨师的一道菜就可以得到厨师的认可。
问是否有一种方案来做材料来得到所有厨师的认可。

Solution

接近 2 -SAT 的裸题。
设第 i 种材料为 $A_i$,$A_i$ 等于 0 代表满式,等于 1 则反之。

所以如果厨师想吃 i 菜的满,j 菜的汉,则约束条件为:
!A[i]||A[j]

以此类推,汉汉:
A[i]||A[j]

满满:
!A[i]||!A[j]

用 2 -SAT 直接判断是否有可行解就 OK 了。

// Code by ajcxsu
// Problem: Food

#include<bits/stdc++.h>
#define CLR(x) memset(x,0,sizeof(x))
#define ASS(x) ((x)+100)
using namespace std;

int n,m;

const int N=210, M=1e5+10;
int h[N],to[M],nexp[M],p=1;
int dfn[N], low[N], idx;
int scc[N], sidx;
int stk[N], top;
bool instk[N];
inline void init() { CLR(h), p=1; CLR(dfn), CLR(low), idx=0; CLR(scc), sidx=0; }
inline void ins(int a,int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

void tarjan(int x) {
    dfn[x]=low[x]=++idx;
    instk[x]=1;
    stk[top++]=x;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            tarjan(to[u]);
            low[x]=min(low[x], low[to[u]]);
        }
        else if(instk[to[u]]) low[x]=min(low[x], dfn[to[u]]);
    if(low[x]==dfn[x]) {
        sidx++;
        do {
            top--;
            scc[stk[top]]=sidx;
            instk[stk[top]]=0;
        } while(stk[top]!=x);
    }
}


int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        init();
        char ch1,ch2;
        int val1,val2;
        for(int i=0;i<m;i++) {
            cin>>ch1>>val1>>ch2>>val2;
            if(ch1!=ch2) {
                if(ch1=='h') swap(val1, val2);
                ins(val1,val2), ins(ASS(val2), ASS(val1));
            }
            else {
                if(ch1=='m') ins(val1, ASS(val2)), ins(val2, ASS(val1));
                else ins(ASS(val1), val2), ins(ASS(val2), val1);
            }
        }

        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        bool ans=1;
        for(int i=1;i<=n && ans;i++) if(scc[i]==scc[ASS(i)]) ans=0;
        if(!ans) cout<<"BAD"<<endl;
        else cout<<"GOOD"<<endl;
    }
    return 0;
}