最小生成树 – Tgotp-Blog

1601: [Usaco2008 Oct]灌水

一开始想了各种奇奇怪怪的算法,最后都死于自己发现都错了题(鬼知道我在想些什么)

最后还是想到了最小生成树,当然不一定是一棵,可能是多颗树, 只要保证两个点间的距离小于这两个点所在集合的最小值就可以合并,然后乱搞搞就好了。

—-我很沙茶的在判断这里错了。。。

c++代码如下:[……]

Read more

1016: [JSOI2008]最小生成树计数

对于同一个权值来说,在不同的最小生成树中出现的次数一样。

然后就枚举就好了,看看能不能加入现有的生成树中/

c++代码如下:

 

1083: [SCOI2005]繁忙的都市

不难想出,最少边数一定是n – 1,按边的价值排序,求最小生成树,搞定。。。

c++代码如下: