我是靠谱客的博主 搞怪日记本，最近开发中收集的这篇文章主要介绍P6378 [PA2010] Riddle（2-sat/前后缀优化建图）P6378 [PA2010] Riddle，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
P6378 [PA2010] Riddle
n个点m条边的无向图，分为k个部分，从每个部分选择恰好一个关键点，使得每条边至少有一个端点是关键点。
首先有这么多的限制，实际上就是一个选或者不选的问题，每条边的限制相当于一个不选就必须选另一个，每个部分的限制就是一旦选择某一个就不能选其他的，所以可以很好地用2-sat来表示。
现在还有一个问题就是如何满足恰好一个关键点，如何避免不选的情况，但是发现如果不选说明这部分点之间没有连边，否则就必须选了，那么我们就可以任选一个点作为关键点，不影响答案。
然后考虑部分限制的图怎么建，本质上就是向除了自己的其他所有非点连边，那么这是一个常见的前后缀优化建图的套路，优化之后图的联通性没有发生变化。
最后
以上就是搞怪日记本为你收集整理的P6378 [PA2010] Riddle（2-sat/前后缀优化建图）P6378 [PA2010] Riddle的全部内容，希望文章能够帮你解决P6378 [PA2010] Riddle（2-sat/前后缀优化建图）P6378 [PA2010] Riddle所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[二分 前缀优化建图 2-SAT] Codeforces 587D. Duff in Mafia](/uploads/reation/bcimg4.png)
![[AT2336] Flags（二分答案+2-SAT+线段树优化建图）](/uploads/reation/bcimg5.png)
![【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解](/uploads/reation/bcimg6.png)
![P6378 [PA2010] Riddle（2-sat/前后缀优化建图）P6378 [PA2010] Riddle](/uploads/reation/bcimg7.png)
![[ 前后缀优化建图 2-SAT ] Codeforces587D Duff in Mafia](/uploads/reation/bcimg8.png)
![[ 2-SAT 线段树 ] Codeforces Gym 100159 Facebook Hacker Cup 2012 I.Unfriending](/uploads/reation/bcimg10.png)
发表评论 取消回复