专门做面包和蛋糕的网站,重庆怎么做平台软件,怎样做自己的手机网站,哪个网站上做ppt比较好P6378 [PA2010] Riddle
n个点m条边的无向图#xff0c;分为k个部分#xff0c;从每个部分选择恰好一个关键点#xff0c;使得每条边至少有一个端点是关键点。
首先有这么多的限制#xff0c;实际上就是一个选或者不选的问题#xff0c;每条边的限制相当于一个不选就必须…P6378 [PA2010] Riddle
n个点m条边的无向图分为k个部分从每个部分选择恰好一个关键点使得每条边至少有一个端点是关键点。
首先有这么多的限制实际上就是一个选或者不选的问题每条边的限制相当于一个不选就必须选另一个每个部分的限制就是一旦选择某一个就不能选其他的所以可以很好地用2-sat来表示。
现在还有一个问题就是如何满足恰好一个关键点如何避免不选的情况但是发现如果不选说明这部分点之间没有连边否则就必须选了那么我们就可以任选一个点作为关键点不影响答案。
然后考虑部分限制的图怎么建本质上就是向除了自己的其他所有非点连边那么这是一个常见的前后缀优化建图的套路优化之后图的联通性没有发生变化。
