bzoj 1086: [SCOI2005]王室联邦 贪心

看起来应该是奇怪的贪心。这题逻辑好奇怪,一个省的省会竟然可以在其他省……

大概说一下,就是子树不小于b就成为一个省。省会为当前点。

这样子每个省都不超过2b。

然后最后可能还有不超过b的城市没有处理。

直接丢尽最后一个省。不超过3b。

dfs处理下就好了。注意每次需要设置一个栈底下面的链接里写的很详细

popoqqq大爷写的很棒了!http://blog.csdn.net/popoqqq/article/details/42772237

发表评论