【NOI2017】游戏

好久没写 $2-sat$ 了……(话说这东西哪里还考过)

题意

有 $3$ 种赛车 $A,B,C$ 和 $4$ 种赛道 $a,b,c,x$,赛车 $A$ 不适用于赛道 $a$,赛车 $B$ 不适用于赛道 $b$,赛车 $C$ 不适用于赛道 $c$。没有赛车不适用于赛道 $x$,但是赛道 $x$ 的数量很少,不超过 $d$ 个。

现在给你一个字符串(只包含 $a,b,c,x$),第 $i$ 位表示第 $i$ 天的赛道种类。

另外有 $m$ 条限制,每条限制是一个四元组 $(i, h_i, j, h_j)$,表示如果第 $i$ 天使用了赛车 $h_i$,第 $j$ 天就必须使用赛车 $h_j$。

请任意构造出一种合法的赛车使用方案,无解则输出 $-1$。

$nle 50000,space mle 100000,space dle 8$

题解

忘了 $2-sat$ 的点这里复习一下

原文地址:https://www.cnblogs.com/scx2015noip-as-php/p/bzoj4945.html