最小生成树

1626: [Usaco2007 Dec]Building Roads 修建道路 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1362 Solved: 541 [Submit][Status][Discuss] Description # Farmer John最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。 所有N(1 <= N <= 1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i, Y_i)的点(0 <= X_i <= 1,000,000；0 <= Y_i <= 1,000,000)，两个农场间道路的长度自然就是代表它们的点之间的距离。现在Farmer John也告诉了你农场间原有的M(1 <= M <= 1,000)条路分别连接了哪两个农场，他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

1601: [Usaco2008 Oct]灌水 # Time Limit: 5 Sec Memory Limit: 162 MB Submit: 1624 Solved: 1059 [Submit][Status][Discuss] Description # Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000)，连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。