【HNOI2010】平面图判定

继续刷。。【写完这个题解还是复习一下的好

首先我们把哈密顿回路展成一个圆。。那么其他的边就是圆上的弧

如果弧相互交叉了我们可以将其中一个翻到外面去。。但是不能同时翻两个

于是在相互交叉的弧之间连边然后黑白染色即可。。

发现边数最大有10000。。

但是伟大的欧拉告诉我们平面图中m<=3n-6

特判掉不符合的,所以边数最多只有594条了。。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz