6378

P6378 [PA2010] Riddle-2sat优化建图 \(n\) 个点 \(m\) 条边的无向图被分成 \(k\) 个部分。每个部分包含一些点。 请选择一些关键点，使得每个部分恰有一个关键点，且每条边至少有一个端点是关键点。 \(1\leq n,m\leq 10^6\) 边的限制 用 \(n ......

知识点：2-SAT，优化建图 Link：https://www.luogu.com.cn/problem/P6378。 2-SAT 前后缀优化建图套路。 对 2-SAT 本质的理解。 简述 给定一 \(n\) 个节点 \(m\) 条边的无向图，该无向图的所有节点被分为了 \(k\) 个部分。 要求选 ......