GoPoux4

分类

未归档(36) 题解(2)

/ 注册

全部文章（共3篇）

题解「Luogu4782 【模板】2-SAT 问题」

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 \(k>2\) 时该问题为 NP 完全的。所以我们只研究 \(k=2\) 的情况。 ——摘自 OI-Wiki 2-SAT问题大多是固定的模型：给定若干个均有两个元素...

2-SAT 题解图论

2020-08-11

0 424

题解「Luogu3209 [HNOI2010]平面图判定」

首先需要了解平面图的定义：如果图 \(G\) 能画在平面 \(S\) 上，即除顶点处外无边相交，则称 \(G\) 可平面嵌入 \(S\) ， \(G\) 为可平面图或平面图。设 \(G\) 是平面图，由 \(G\) 的边将 \(G\) 所在的平面划分成若干个区域，每个区域称为 \(G\)...

题解 2-SAT 图论

2020-08-19

0 468

总结「斯坦纳树」

转载注明来源：https://www.cnblogs.com/syc233/p/13650130.html 姑且当作状压DP的复习了。斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点...

总结图论动态规划

2020-09-11

0 472