web analytics

仲夏之夜 并查集

描述

Pty开始展开他的想象力:在这片绚丽的星空图上,有n颗星星,从1到n进行编号。现在有n-1条星际航道(双向)把这n颗星星给连接了起来。

每条星际航道都有一个过路费(费用是正整数),设这n-1条航道的过路费之和是V。Pty想让每两个星星之间都连一条星际航道,但是要求在连完之后:

对于任意一种能把n颗星星连接起来的m条航道(这m条航道和现存的航道不完全相同),满足这m条航道的过路费之和>V。

请你告诉Pty:能满足他条件的方案里:图中所有的星级航道过路费之和最小是多少?

Pty将告诉你:这n-1条航道所连接的点,和每条航道的过路费。

例:

N=4时,下图为某个图的n-1条航道及过路费:

那么此图的所有星级航道的过路费之和最小为:17(如下图)

输入输入文件summer.in包含n行:
第1行是整数n,表示星际图星星的个数。
接下来共n-1行描述这个图的n-1条航道:
每行3个整数:v,u,t表示这条星际航道连接v,u两颗星星,它的过路费是t。输出输出文件summer.out包含1行:
M(整个图的最小的星级航道过路费之和)样例输入4 1 2 1 2 4 2 3 4 3样例输出17提示30%的数据满足:1<=n<=100
70%的数据满足:1<=n<=30000
100%的数据满足:1<=n<=100000,t<=100

 

分析:

首先要明白这道题是建完全图的思路走的。

因为给出了个严格的最小生成树,所以往里面加点的时候,就得比集合里的最大的数+1.

用并查集来维护点集,然后加在最小生成树上的边的时候合并两个集合,之间的两两的点都加上边。

 

Post a Comment

You must be logged in to post a comment.