~bzoj1823
第一次接触2-SAT——SAT,即适定性（Satisfiability）的缩写。像名称所说，即满足需求的可能性问题，而k-SAT即每个人有k种需求，已经证明k>2时是一个NP完全问题。所以现在常见的考法便是2-SAT。
这一道题目算是一道裸的2-SAT问题。每一个人有两种需求，那么我们就将每一种食物拆成两个点，一个代表m,一个代表h，可以注意到满足所有人的需求即如果满足不了其中一个，必须满足另一个，所以我们建图的方法为从无法满足要求的点连向必须满足的点，代表若一个点不符合要求，必然走向后续的决策。那么问题的答案相比到这里已经比较明了了。我们就应当在这张图上求出强连通分量，看是否有一个点的两个拆点都存在于这张图上。若是如此，就说明无法满足要求。
#include <bits/stdc++.h>using namespace std;#define maxn 100000int T, cnt, cnp = 1, n, m, low[maxn], dfn[maxn], num[maxn], timer, head[maxn];bool flag, mark[maxn], vis[maxn];stack <int> st;struct edge{ ???int to, last;}E[maxn];int read(){ ???int x = 0; ???char c; ???c = getchar(); ???while(c < ‘0‘ || c > ‘9‘) c = getchar(); ???while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); ???return x;}void add(int u, int v){ ???E[cnp].to = v, E[cnp].last = head[u], head[u] = cnp ++;}void tarjan(int u){ ???dfn[u] = low[u] = ++ timer; ???vis[u] = true, mark[u] = true; ???st.push(u); ???for(int i = head[u]; i; i = E[i].last) ???{ ???????int v = E[i].to; ???????if(vis[v]) ??????? { if(mark[v] && low[u] > dfn[v]) low[u] = dfn[v]; } ???????else ????????{ ???????????tarjan(v); ???????????low[u] = min(low[u], low[v]); ???????} ???} ???if(dfn[u] == low[u]) ???{ ???????++ cnt; ???????int j; ???????do ???????{ ???????????j = st.top(); ???????????st.pop(); ???????????mark[j] = false; ???????????num[j] = cnt; ???????}while(!st.empty() && j != u); ???}}void init(){ ???memset(vis, 0, sizeof(vis)); ???memset(head, 0, sizeof(head)); ???cnp = 1, timer = 0; ???flag = false;}int main(){ ???T = read(); ???while(T --) ???{ ???????n = read(), m = read(); ???????init(); ???????for(int i = 1; i <= m; i ++) ???????{ ???????????char c1, c2; ???????????int d1, d2; ???????????cin >> c1 >> d1 >> c2 >> d2; ???????????int a = 0, b = 0; ???????????a += (c1 == ‘h‘), b += (c2 == ‘h‘); ???????????add(((2 * d2) + b) ^ 1, (2 * d1) + a); ???????????add(((2 * d1) + a) ^ 1, 2 * d2 + b); ???????} ???????for(int i = 2; i <= 2 * n + 1; i ++) ???????????if(!vis[i]) tarjan(i); ???????for(int i = 2; i <= 2 * n; i += 2) ???????????if(num[i] == num[i ^ 1]) ????????????{ ???????????????printf("BAD\n"); ???????????????flag = true; break; ???????????} ???????if(!flag) printf("GOOD\n"); ???} ???return 0;}【题解】JSOI2010满汉全席
原文地址：https://www.cnblogs.com/twilight-sx/p/8436914.html