题意：

Let's go home

Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1358 Accepted Submission(s): 522

Problem Description

小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。

—— 余光中

集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。

Input

第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。

接下来有T行，每行三个整数，表示一个队的队员编号，第一个队员就是该队队长。

然后有M行，每行两个整数，表示一对队员的编号。

每个队员只属于一个队。队员编号从0开始。

Output

可行输出yes，否则输出no，以EOF为结束。

Sample Input

1 2
0 1 2
0 1
1 2

2 4
0 1 2
3 4 5
0 3
0 4
1 3
1 4

Sample Output

yes
no

思路：

基础的2sat,不会的建议看根据对称性解析2sat的那个，把队长和两个队员看成基本的一对，然后再把排斥的那个看成排斥的一对，输入的时候记得吧两个队员hash成一个人就行了。

#include<stdio.h>

#include<string.h>

#include<stack>

#define N_node 30000 + 100

#define N_edge 50000 + 100



using namespace std;

typedef struct

{

   int to ,next;

}STAR;

STAR E1[N_edge] ,E2[N_edge];

int list1[N_node] ,list2[N_node] ,tot;

int Belong[N_node] ,cnt;

int mark[N_node] ,id[N_node];

stack<int>st;

void add(int a ,int b)

{

   E1[++tot].to = b;

   E1[tot].next = list1[a];

   list1[a] = tot;

   E2[tot].to = a;

   E2[tot].next = list2[b];

   list2[b] = tot;

}

void DFS1(int s)

{

   mark[s] = 1;

   for(int k = list1[s] ;k ;k = E1[k].next)

   {

      int xin = E1[k].to;

      if(!mark[xin]) DFS1(xin);

   }

   st.push(s);

}

void DFS2(int s)

{

   mark[s] = 1;

   Belong[s] = cnt;

   for(int k = list2[s] ;k ;k = E2[k].next)

   {

      int xin = E2[k].to;

      if(!mark[xin]) DFS2(xin);

   }

}

int main ()

{

   int n ,m ,i ,a ,b ,c;

   while(~scanf("%d %d" ,&n ,&m))

   {

      for(i = 0 ;i < n ;i ++)

      {

         scanf("%d %d %d" ,&a ,&b ,&c);

         id[a] = i * 2;

         id[b] = id[c] = i * 2 + 1;

      }

      memset(list1 ,0 ,sizeof(list1));

      memset(list2 ,0 ,sizeof(list2));

      tot = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d" ,&a ,&b);

         add(id[a] ,id[b]^1);

         add(id[b] ,id[a]^1);

      }

      memset(mark ,0 ,sizeof(mark));

      while(!st.empty())st.pop();

      for(i = 0 ;i < n * 2 ;i ++)

      if(!mark[i]) DFS1(i);

      memset(mark ,0 ,sizeof(mark));

      cnt = 0;

      while(!st.empty())

      {

         int xin = st.top();

         st.pop();

         if(mark[xin]) continue;

         ++cnt;

         DFS2(xin);

      }

      int mk = 0;

      for(i = 0 ;i < n * 2 ;i += 2)

      {

         if(Belong[i]  == Belong[i^1])

         mk = 1;

      }

      mk ? puts("no") : puts("yes");

   }

   return 0;

}

巴特西

hdu1824 基础2sat

Let's go home

最新文章

热门文章