Luogu P5332 [JSOI2019]精准预测

标签：link   getchar   main   ext   row   amp   保留   优化   while   

Link
对于火星人\(u\)，在时间点\(t\)，我们将其拆成两个点\((u,t,0),(u,t,1)\)表示它的存活状态。
考虑用\(\text{2-SAT}\)来表示限制。
那么此时我们有\((i,t,0)\rightarrow(i,t+1,0),(i,t+1,1)\rightarrow(i,t,1)\)两条边。
对于限制\((0,t,u,v)\)，我们连\((u,t,0)\rightarrow(v,t+1,0),(v,t+1,1)\rightarrow(u,t,1)\)。
对于限制\((1,t,u,c)\)，我们连\((u,t,1)\rightarrow(v,t,0),(v,t,1)\rightarrow(u,t,0)\)。
那么我们要求的就是在选择\((u,T+1,0)\)时有多少个\((v,T+1,1)\)必定被选择，即有多少个\((v,T+1,1)\)在\((u,T+1,0)\)的后继中。
注意到对于每个火星人而言，我们可以只保留它的在时刻\(T+1\)的点和作为\(u\)限制时的点，那么点数就是\(2(n+m)\)了。
求答案用\(\text{bitset}\)优化\(\text{DAG}\)上传递闭包即可，时空复杂度均为\(O(\frac{n^2}{\omega})\)（认为\(n,m\)同阶）。
空间开不下可以分多次跑。

#include

Luogu P5332 [JSOI2019]精准预测

标签：link   getchar   main   ext   row   amp   保留   优化   while   

原文地址：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12933959.html