Java教程

#4973. [Lydsy1708月赛]比特战争

本文主要是介绍#4973. [Lydsy1708月赛]比特战争，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

4973. [Lydsy1708月赛]比特战争
这个题确实是有点妙...
首先我们可以考虑最终的答案是怎么样的，肯定是若干个连通块，和一些单独的点，考虑它们对答案的贡献分别是什么，单独的点肯定是\(a_i*b_i\)，连通块的话考虑所有的点和所有的边都被占领了，所有贡献为\(max(maxa_i,maxc_i)*minb_i\)，简单来时候就是就是在某一个\(b_i\)最小的国家降落足够多的士兵，然后带着这些士兵将这个连通块全部占领。接下来考虑答案具有哪些性质？可以看到由于\(maxc_i\)的存在,我们希望连通块内的边权足够小。那么就是说这个连通块内的边一定是当前连通块内的最小生成树。(联通，且最大边权最小)。那我们可以做一下kruskal，在枚举每个边的时候维护每个连通块内的\(maxa_i,max_ci,minb_i\)，然后将每个点都先当成一个单独的连通块，做kruskal，来维护答案与连通块。

这篇关于#4973. [Lydsy1708月赛]比特战争的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航