hdu 4115 Eliminate the Conflict (3-sat ??? no! it's a 2-sat pro.)

坑爹：

看到各种冲突，当然第一反映是2-sat，但是这有三种情况啊，貌似不能满足布尔型约束吧。。。gg吧， 没法做。。。

反思：

传统2-sat是，i拆为两个节点，为真对应i节点，为假对应i+n节点。这个题有三种不同的bool变量可以将每个点拆成6个点。

石头：i*6+0 | i*6+1;

剪刀：i*6+2 | i*6+3;

布： i*6+4 | i*6+5.

这样就能轻松解决各种约束了。。。

#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define MP make_pair#define eps 1e-8using namespace std;const int maxn = 60010;int T, n, m, v, a, b, k;vector<int> G[maxn];int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;stack<int> s;void dfs(int u) {  pre[u] = lowlink[u] = ++dfs_clock;  s.push(u);  for(int i = 0; i < G[u].size(); i++) {    int v = G[u][i];    if(!pre[v]) {      dfs(v);      lowlink[u] = min(lowlink[u], lowlink[v]);    } else if(!sccno[v]) {      lowlink[u] = min(lowlink[u], pre[v]);    }  }  if(lowlink[u] == pre[u]) {    scc_cnt++;    for(;;) {      int x = s.top(); s.pop();      sccno[x] = scc_cnt;      if(x == u) break;    }  }}bool solve(int n){  dfs_clock = scc_cnt = 0;  CLR(sccno, 0); CLR(pre, 0);  REP(i, n*6) if(!pre[i]) dfs(i);  REP(i, n)  {      if(sccno[i*6] == sccno[i*6+1]) return false;      if(sccno[i*6+2] == sccno[i*6+3]) return false;      if(sccno[i*6+4] == sccno[i*6+5]) return false;  }  return true;};//石头inline int R(int a) { return a*6; }inline int rR(int a) { return R(a) + 1; }//剪刀inline int S(int a) { return a*6 + 2; }inline int rS(int a) { return S(a) + 1; }//布inline int P(int a) { return a*6 + 4; }inline int rP(int a) { return P(a) + 1; }inline void add(int a, int b) { G[a].PB(b); }int main(){    scanf("%d", &T);    FF(kase, 1, T+1)    {        scanf("%d%d", &n, &m);        REP(i, n*6) G[i].clear();        REP(i, n)        {            add(R(i), rS(i));            add(R(i), rP(i));            add(S(i), rR(i));            add(S(i), rP(i));            add(P(i), rS(i));            add(P(i), rR(i));        }        REP(i, n)        {            scanf("%d", &v);            if(v == 1)            {                add(rR(i), P(i));                add(rP(i), R(i));            }            else if(v == 2)            {                add(rS(i), R(i));                add(rR(i), S(i));            }            else            {                add(rP(i), S(i));                add(rS(i), P(i));            }        }        REP(i, m)        {            scanf("%d%d%d", &a, &b, &k); a--; b--;            if(k)            {                add(R(a), rR(b));                add(R(b), rR(a));                add(S(a), rS(b));                add(S(b), rS(a));                add(P(a), rP(b));                add(P(b), rP(a));            }            else            {                add(R(a), R(b));                add(R(b), R(a));                add(S(a), S(b));                add(S(b), S(a));                add(P(a), P(b));                add(P(b), P(a));            }        }        printf("Case #%d: %s\n", kase, solve(n) ? "yes" : "no");    }    return 0;}