BZOJ4945 - [NOI2017] 游戏

洛谷 SPJ 坏了,一个月了没修好。怎么回事啊?

UPD: QQ 群里 @ 了一下 chen_zhe 竟然很快修好了

回到正题:本题是 2-SAT 裸题,做之前可以参考一下洛谷的模板题,下面假装你已经看过并 AC 了那道题。

对于 $a$ 、 $b$ 、 $c$ 三种地图,都是不允许一辆车,而允许另外两辆。对于 $x$ 地图,显然不能交给 2-SAT 算法解决,暴力枚举他是 $a$ 地图还是 $b$ 地图(如果 $a$ 和 $b$ 都不行那么 $c$ 也不行)。

关于连边,用 $u$ 表示第 $i$ 场游戏使用赛车 $h_i$ 所对应的点,$v$ 表示 第 $j$ 场游戏赛车 $h_j$ 所对应的点,$u’$ 和 $v’$ 则表示对应地图可以使用的另一辆赛车所对应的点。

如果 $h_i$ 不符合第 $i$ 张地图的限制条件,那么这种约束肯定不会遇到,跳过即可。

如果 $h_j$ 不符合第 $j$ 张地图的限制条件,那么说明 $i$ 的这种情况肯定不能取到,就从 $u$ 向 $u’$ 连一条边。

否则说明如果取了 $h_i$ 就一定要取 $h_j$ ,连接边 $u$ 到 $v$ 和 $u’$ 到 $v’$ 即可。

另外,由于 2-SAT 要跑很多遍,所以请注意清空数组(我不会告诉你我没有清空 dfn 拿到了 $90$ 分的好成绩)。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×