标题效果：有着n材料的种类，m陪审团。
每种材料具有两种不同的方法。每个法官都有两个标准。做出来的每一个法官的菜必须至少满足一个需求。
问：是否有这样一个程序。
思考：2-SAT经典的内置图形问题。因为每种材料只能有两种方法，约束条件通常就想到2-SAT。每个评委必须至少满足一种。这就是建图的条件。
所以连边A‘ -> B
B’ -> A
这样表示的是假设A不能满足某个评委，那么就必须让b满足这个评委。
然后就是Tarjan缩点，推断是否有个菜品的两种做法在一个scc中，若有就是无解，没有就是有解。
CDOE：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 5010
using namespace std; int cases;
int points,cnt; int head[MAX],_total;
int _next[MAX],aim[MAX]; int dfn[MAX],low[MAX],total;
int stack[MAX],top;
bool in_stack[MAX];
int changed[MAX],scc; char c1,c2; inline void Initialize();
inline void Add(int x,int y);
void Tarjan(int x); int main()
{
for(cin >> cases;cases; --cases) {
scanf("%d%d",&points,&cnt);
Initialize();
for(int x,y,i = 1;i <= cnt; ++i) {
getchar();
scanf("%c%d %c%d",&c1,&x,&c2,&y);
x = (x << 1) + (c1 == 'h');
y = (y << 1) + (c2 == 'h');
Add(x^1,y);
Add(y^1,x);
}
for(int i = 2;i <= (points << 1|1); ++i)
if(!dfn[i]) Tarjan(i);
bool flag = true;
for(int i = 1;i <= points; ++i)
if(changed[i << 1] == changed[i << 1|1])
flag = false;
if(flag) puts("GOOD");
else puts("BAD");
}
return 0;
} inline void Initialize()
{
total = _total = top = scc =0;
memset(dfn,0,sizeof(dfn));
memset(head,0,sizeof(head));
memset(in_stack,false,sizeof(in_stack));
} inline void Add(int x,int y)
{
_next[++_total] = head[x];
aim[_total] = y;
head[x] = _total;
} void Tarjan(int x)
{
dfn[x] = low[x] = ++total;
stack[++top] = x;
in_stack[x] = true;
for(int i = head[x];i;i = _next[i]) {
if(!dfn[aim[i]])
Tarjan(aim[i]),low[x] = min(low[x],low[aim[i]]);
else if(in_stack[aim[i]])
low[x] = min(low[x],dfn[aim[i]]);
}
if(low[x] == dfn[x]) {
scc++;
int temp;
do {
temp = stack[top--];
changed[temp] = scc;
in_stack[temp] = false;
}while(temp != x);
}
}
版权声明：本文博主原创文章，博客，未经同意不得转载。