中问题 题意略
和HDOJ 3062一样
这里 每个队员都有 选 和 不选 两种， 即 上篇所说的$x$和$x’$
建图：队长(a)留下或者其余两名队员(b、c)同时留下
那么就是$a' \Rightarrow b$ 、 $a' \Rightarrow c$ (队长不在 b必须在， 队长不在 c必须在)
以及$b' \Rightarrow a$ 、$c' \Rightarrow a$ (b不在 队长必须在，c不在 队长必须在)
每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家
那么就是$A \Rightarrow B’$ (A在 则B必须不在) 以及 $B \Rightarrow A'$ (B在 则A必须不在)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
#define INF 0x3f3f3f3f const int N=*;
const int M=N*N;
//注意n是拆点后的大小 即 n <<= 1 N为点数(注意要翻倍) M为边数 i&1=0为i真 i&1=1为i假
struct Edge
{
int to, nex;
}edge[M];
//注意 N M 要修改
int head[N], edgenum;
void addedge(int u, int v)
{
Edge E={v, head[u]};
edge[edgenum]=E;
head[u]=edgenum++;
} bool mark[N];
int Stack[N], top;
void init()
{
memset(head, -, sizeof(head));
edgenum=;
memset(mark, , sizeof(mark));
} bool dfs(int x)
{
if(mark[x^])
return false;//一定是拆点的点先判断
if(mark[x])
return true;
mark[x]=true;
Stack[top++]=x;
for(int i=head[x];i!=-;i=edge[i].nex)
if(!dfs(edge[i].to))
return false; return true;
} bool solve(int n)
{
for(int i=;i<n;i+=)
if(!mark[i] && !mark[i^])
{
top=;
if(!dfs(i))
{
while(top)
mark[Stack[--top]]=false;
if(!dfs(i^))
return false;
}
}
return true;
} int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
int nn=n*;
init();
while(n--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a*+, b*);
addedge(a*+, c*);
addedge(b*+, a*);
addedge(c*+, a*);
}
while(m--)
{
int x, y;
scanf("%d%d", &x, &y);
addedge(x*, y*+);
addedge(y*, x*+);
}
solve(nn)? puts("yes"): puts("no");
}
return ;
}
HDOJ 1824