Trobojnica

· · 个人记录

题意：

有一个多边形，边上染了三种颜色。试找到一个染色后的三角剖分，使得每个三角形三条边不同色。

题解：

显然有两个情况是无解的：同色多边形和某一种颜色边的条数和 $n$ 不同奇偶。 同色显然。奇偶的证明是内部每条边两次贡献，外部一次，最终一共 $n-2$ 个三角形，每个三角形要算一次。 构造只要保证如果有一个合法的解，就一定能走那个决策路径就行。所以为了不出现同色，尽量让三种颜色的边条数差不多，我的做法是开三个 $set$ 表示两边颜色分别为 $1-2,2-3,1-3$ 的顶点，每次让新加的那条边是出现次数最少或次少的颜色即可。 对于奇偶性，由于每次连边 $n-1$ ，两种颜色 $-1$ ，一种颜色 $+1$ ，所以只要开始奇偶相同，做的过程就一定不会不同。