luogu题解 P4171 【[JSOI2010]满汉全席】

写在前面

不会吧不会吧，这么裸的2-SAT都看不出来？ 经验题

题目传送门

Solution

2-SAT处理

关于什么是2-SAT，详见Oiwiki

简单来说，2-SAT问题的形式是给一堆条件，每个条件中有两个小条件，不过只需要满足其中一种

题目中说评委的两个条件只需要满足一个即可，然后每种材料又有满式和汉式两种选择

这不显然让我们打2-SAT？可能也有其他神仙做法

而2-SAT主要考察建图这一块，我们用 \(0 \sim n\) 表示满式，用 \(n+1 \sim 2n\) 表示汉式，用 \(x^{-1}\) 表示 \(x\) 的另一种菜式

那么对于任意一个条件 \((a_i,b_i)\)，

• 首先让我们满足 \(a_i\) 而不满足 \(b_i\) ，那就从 \(a_i\) 向 \(b_i^{-1}\) 连一条边

• 然后让我们满足 \(b_i\) 而不满足 \(a_i\) ，那就从 \(b_i\) 向 \(a_i^{-1}\) 连一条边

（别搞混了调半天）

字符串处理

暴力处理即可，判断第一个字符确定满式还是汉式

扫一遍字符串取出是第几号菜，然后按上面的方式加边

答案判断

用强连通分量缩点

缩点后，如果存在同一菜品出现在同一强联通分量里，那就不能满足

否则就可以满足

大体思路就这些，看代码吧

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<>(u + 1)>>(v + 1);
//			cout<<(u + 1)<<" "<<(v + 1)<