TIOJ:: 1149 . 4.滿漢全席

http://tioj.ck.tp.edu.tw/problems/1149
經典問題，2-sat。


題目是說，有很多種材料，每種都可以選擇作成漢式或是滿式，但是同時只能選擇做成一種。
同時有很多位裁判，每位裁判會指定兩種菜色要做成漢式或是滿式，而參賽者至少要滿足其中一個條件，不然會被淘汰，而主辦單位為了避免沒有任何方式可以滿足所有裁判的要求，要先檢查一下有沒有裁判的要求會衝突到。

先觀察一下，就會發現問題可以寫成一個2-sat問題，也就是一串布林運算式，而我們必須讓他結果為True。

因為2-sat問題的圖論解法(建圖、縮點、找解)之前寫過了，加上這題範圍很小(裁判數和菜數都不超過15)，所以就直接爆搜了XDD。

先把每道菜當成一個變數(可以是True或False，是滿式或是不是滿式)，每個裁判的條件可以當成 X or Y，只要滿足一項就可以了。
然後跑完2的15次方種可能，每種可能直接檢查是否每個裁判都是滿足的，這樣就解決了。

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=(l);i<(n);i++)
using namespace std;
const int N = 15;
typedef pair<int,bool> PIB;
PIB D[N*2];
inline bool getbit(int h,int p){
    return h&(1<<p);
}
inline bool check(int h,int m){
    F(m){
        // cout<<"DD "<<getbit(h,D[i*2].first)<<' '<<D[i*2].second<<endl;
        // cout<<"   "<<getbit(h,D[i*2+1].first)<<' '<<D[i*2+1].second<<endl;
        if(getbit(h,D[i*2].first)^D[i*2].second);
        else if(getbit(h,D[i*2+1].first)^D[i*2+1].second);
        else return false;
    }
    return true;
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,m,a;
    char c;
    cin>>t;
    while(t--){
        cin>>n>>m;
        F(m){
            cin>>c>>a;
            D[i*2] = PIB(a-1,c=='m');
            cin>>c>>a;
            D[i*2+1] = PIB(a-1,c=='m');
        }
        bool ans = false;
        F(1<<n){
            // cout<<i<<endl;
            if(check(i,m)){
                ans = true;
                break;
            }
        }
        cout<<(ans?"GOOD\n":"BAD\n");
        //cout<<flush;
    }
}