最近考试【最小差异值】这个问题出现次数还蛮多的,之前思路想错了,直接报0(额……就是打0分的意思啊),这次考试才终于AC掉了。

先上问题吧。

最小差异值
【问题描述】
P 省刚经历一场不小的地震,所有城市之间的道路都损坏掉了,所以省长想
请你将城市之间的道路重修一遍。
因为很多城市之间的地基都被地震破坏导致不能修公路了,所以省长给定了
你一些城市对,在这些城市对之间可以修公路,并且都有相应的价格。而且因为
施工队伍有限,所以省长要求用尽量少的道路将所有的城市连通起来,这样施工
量就可以尽量少, 道路可视为无向边, 且数据保证至少有一种连通的方案。 不过,
省长为了表示自己的公正无私,要求在满足上述条件的情况下,选择一种方案,
使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小, 即使这样的方
案会使总价提升很多也没关系。
那么,请你尽快地安排一种合理的方案,满足省长的要求。
【输入格式】
第一行两个数 N,M,表示城市的个数以及可以修的公路数;
第二行开始 M 行,每行三个数 a,b,c,表示 a,b 之间可以修一条价值 c 的无向
道路。
【输出格式】
一个数表示该方案中最大边减去最小边的值,要求要尽量的小。
【样例输入】
5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422
【样例输出】
1686
【样例说明】
选第 4,5,6,9 条边即可。
【数据说明】
30%数据满足 N<=M<=20
100%数据满足 N<=M<=5000,0<c<=50000;

嗯,看完题目,先忍住心中莫名的怒火(这省长真是聪(zhi)明(zhang)为什么不选最便宜的路径(那样就可以直接最小生成树了呀)修路啊!真是……),分析一下题目。

要路的条数最少,那路的条数就是N(城市数目)-1,说白了就是要你生成一棵树。

还要求最大费用路和最小费用路的差最小。怎么让路与路之间的费用差最小呢?看看下面:

按输入样例来看:

路的费用:

9384

887

2778

6916

7794

8336

5387

493

6650

1422

这样子无序地排列,差值会比较大。

其实用数学的思维想一想就知道了,当路已经按照费用排好序的时候,它们之间的差会是最小的:

493

887

1422

2778

5387

6650

6916

7794

8336

9384
这样排序以后,差值不就是最小的了吗?(实在不好解释啊,额,真的,用数学的思维想一想啊!)

这里的排序从小到大还是从大到小排序都是一样的,但是后面我们都以从小到大排序来讲。

排好序了怎么办呢?

其实我也不知道啊,啊哈哈哈哈。我这里用的是枚举,比如这里,就从排好序的第一条路开始,一直到第M-N+1条路(为什么是M-N+1呢?后面会讲的。),枚举出来,以这条枚举出来的路为生成树的第一条边生成一棵树。额,讲不清楚,上图算了:



以此类推。现在知道为什么只枚举到第M-N+1条路了吗?对啊,如果目前枚举的这条路加上剩下的所有路的条数小于了N-1条,比如在样例中,你枚举到了第7条(7794),然后你用3条边生成一个有5个节点的树肯定是不行的。

最后把保存下来的最小费用差输出即可!

贴上满分代码(又开始飘了):