![【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解](/uploads/reation/bcimg6.png)
【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解
题目概述有 nn 个点， mm 条边和 KK 个国家（国家里的点已知）。每个国家只能选一个点作为首都，并且要保证最后所有边的两端至少有一个点是首都，问是否存在方案。解题报告每个点是首都或不是首都，只有两个状态，所以是2-SAT问题。mm 条边的限制很容易转化，就是每个国家只能选一个点为首都比较奇怪。 其实这是典型的前后缀优化建图，这里以前缀优化建图为例： 首先我们先增加 nn 个点，令 ii 的
