抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

传送门 考虑先把这张图的最小生成树GGG建出来,假设查询的边为EEE, 发现: 1.1.1.如果EEE本来就在GGG里面,那么直接输出GGG的边权和,因为没有比这个更优的解。 2.2.2.如果EEE不在GGG里面,那么EEE一定和GGG 形成一个环,根据贪心的原则,我们把这条环上面最大边权的边删去,这样新的图仍然是一棵树,而且边权和最小。 在实际操作过程中,我们并不用找到那个环,可以这么想,...

传送门 这题其实有两种做法: 1.1.1. 我一开始想到的是二分加并查集,考虑二分最近部落的距离,如果两点iii,jjj距离小于等于midmidmid那么连边,并查集维护,最后统计有多少集合。 考虑如何证明单调性:如果两点iii,jjj在mid1mid1mid1情况下能连边,那么在mid2mid2mid2情况下也能连边(mid2>mid1mid2>mid1mid2>mid1...

我们把自己建了水库的节点称为AAA类节点,通过其他农田饮水的称为BBB类节点。 考虑最后生成的图,根据贪心,图中肯定没有环,所以这个图是一个森林,且森林中的每棵树都有且仅有一个AAA类节点,若大于111则造成浪费。 考虑把森林变成树,我们建立超级源点000号节点,和图中每个节点iii相连,边权就可以设为wiw_iwi​, 然后节点iii,节点jjj连边权为pijp_{ij}pij​的边即可。...