[BZOJ1232][[Usaco2008Nov]安慰奶牛cheer(MST)

时间:2022-05-08 07:58:09

题目:http://hzwer.com/2493.html

分析:对于每条边,贡献的价值是这条边的边权加上这条边连接的两点的权值,所以可以把每条边的边权加上两顶点的点权作为新的边权,然后跑个最小生成树就行了,要注意作为树根的那个点还要再经过一次,所以找个点权最小的点作为树根,再加上这个树根的点权。