标题效果：有着n材料的种类，m陪审团。
每种材料具有两种不同的方法。每个法官都有两个标准。做出来的每一个法官的菜必须至少满足一个需求。
问：是否有这样一个程序。
思考：2-SAT经典的内置图形问题。因为每种材料只能有两种方法，约束条件通常就想到2-SAT。每个评委必须至少满足一种。这就是建图的条件。
所以连边A‘ -> B
B’ -> A
这样表示的是假设A不能满足某个评委，那么就必须让b满足这个评委。
然后就是Tarjan缩点，推断是否有个菜品的两种做法在一个scc中，若有就是无解，没有就是有解。
CDOE：
#include#include #include #include #define MAX 5010using 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); }}
版权声明：本文博主原创文章，博客，未经同意不得转载。