mengbierr

一个蒟蒻的博客

3月20

Codeforces429E. Points and Segments

题目大意

给出n条线段[li,ri],你可以将每条线段包含的点染成红色或蓝色,求一种方案使得每个点上两种颜色被染次数相差不超过1.无解输出“-1”。

题解

对于每个线段,连一条li到ri+1的双向边,这样求欧拉回路就能保证每个点的红蓝染色次数相等,如果不能求出欧拉回路,那么将相邻的度数为奇数的点连边,这样每个点上人为连的边不超过1个,保证了相差不超过1.

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注