mengbierr

一个蒟蒻的博客

2月26

bzoj2689: 堡垒

考虑每个度数为2的点,它与相邻的两个点形成一个三角形,显然每个三角形中至少要选两个点,则选另外两个点一定是最优的。利用拓扑排序即可解决每个三角形,如果当前点被选中则直接跳过。

 

发表评论

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