hdu4115 Eliminate the Conflict--2-sat

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=4115​​

题意：x，y两个人玩剪刀石头布，玩n局，1代表剪刀，2代表石头，3代表布。先给出y的n局每次所出的，再给出m行对x的出法的限制，每行三个数字，a，b，k，如果k为0，表示x这个人的第a和b局出法相同；k若是1，则不同。如果x的出法矛盾或者只要输一局，输出no，不然输出yes。

分析：对于每局，x的出法有两种，和局和胜利局。再根据m行的限制进行建图，

然后会有一些矛盾对，假设第a次可以出a1，a2， 第b次可以出b1和b2
如果第a次和b次要求相同， 但是a1和b1不同，说明这个矛盾，建立连接 a1—>b2, b1—>a2
同理，第a次和b次要求不相同，但是a1和b2相同，说明这个矛盾，建立链接a1—>b1,  b2—>a2

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

int t;
int n, m;
int cnt, index;
vector<int> vec[20005];
stack<int> s;
int dfn[20005];
int low[20005];
int belong[20005];
int a[10005];
int b[10005][2];
bool inStack[20005];

void tarjan(int u)
{
  low[u] = dfn[u] = ++index;
  s.push(u);
  inStack[u] = 1;
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (!dfn[v])
    {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
    else if (inStack[v])
      low[u] = min(low[u], dfn[v]);
  }

  if (low[u] == dfn[u])
  {
    int p;
    cnt++;
    do
    {
      p = s.top();
      s.pop();
      inStack[p] = 0;
      belong[p] = cnt;
    } while (p != u);
  }
}

void solve()
{
  memset(dfn, 0, sizeof(dfn));
  for (int i = 2; i <= 2 * n + 1; i++)
    if (!dfn[i])
      tarjan(i);

  for (int i = 2; i <= 2 * n + 1;i=i+2)
    if (belong[i] == belong[i + 1])
    {
      printf("no\n");
      return;
    }
  printf("yes\n");
}

int main()
{
  scanf("%d", &t);
  for (int Case = 1; Case <= t; Case++)
  {
    scanf("%d%d", &n, &m);

    //init
    cnt = index = 0;
    for (int i = 2; i <= 2 * n + 1; i++)
    {
      vec[i].clear();
      inStack[i] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &a[i]);
      b[i][0] = a[i];//两个办法可以赢，一个是和局
      b[i][1] = (a[i] + 1 == 3) ? 3 : (a[i] + 1) % 3;//一个是胜局
    }
    int x, y, z;
    for (int i = 1; i <= m; i++)
    {
      scanf("%d%d%d", &x, &y, &z);
      if (z == 0)//相同
      {
        if (b[x][0] != b[y][0])
          vec[x * 2].push_back(y * 2 + 1), vec[y * 2].push_back(x * 2 + 1);
        if (b[x][0] != b[y][1])
          vec[x * 2].push_back(y * 2), vec[y * 2 + 1].push_back(x * 2 + 1);
        if (b[x][1] != b[y][0])
          vec[x * 2 + 1].push_back(y * 2 + 1), vec[y * 2].push_back(x * 2);
        if (b[x][1] != b[y][1])
          vec[x * 2 + 1].push_back(y * 2), vec[y * 2 + 1].push_back(x * 2);
      }
      else//不相同
      {
        if (b[x][0] == b[y][0])
          vec[x * 2].push_back(y * 2 + 1), vec[y * 2].push_back(x * 2 + 1);
        if (b[x][0] == b[y][1])
          vec[x * 2].push_back(y * 2), vec[y * 2 + 1].push_back(x * 2 + 1);
        if (b[x][1] == b[y][0])
          vec[x * 2 + 1].push_back(y * 2 + 1), vec[y * 2].push_back(x * 2);
        if (b[x][1] == b[y][1])
          vec[x * 2 + 1].push_back(y * 2), vec[y * 2 + 1].push_back(x * 2);
      }
    }

    printf("Case #%d: ", Case);
    solve();
  }

  return 0;
}