[Acwing] 1146.新的开始 Kruskal+虚拟源点

前言

新的开始,的确是新的开始了… 传送门 :

思路

我们发现这题不仅仅是维护边权了,其中还需要加入一个点权,怎么做呢?将每一条边都加上点权嘛？(貌似可行hh

当然我们还可以加入虚拟源点

虚拟源点 到 其他点的边权就是该点的 点权

因此这样子建完图之后直接跑一遍Kruskal就行了

CODE

void init()
{
	for(int i=0;i