BZOJ 1626: [Usaco2007 Dec]Building Roads 修建道路 (MST)

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)条路分别连接了哪两个农场,他希望你计算一下,为了使得所有农场连通,他所需建造道路的最小总长是多少。

Input

* 第1行: 2个用空格隔开的整数:N 和 M

* 第2..N+1行: 第i+1行为2个用空格隔开的整数:X_i、Y_i * 第N+2..N+M+2行: 每行用2个以空格隔开的整数i、j描述了一条已有的道路, 这条道路连接了农场i和农场j

Output

* 第1行: 输出使所有农场连通所需建设道路的最小总长,保留2位小数,不必做 任何额外的取整操作。为了避免精度误差,计算农场间距离及答案时 请使用64位实型变量

Sample Input

4 1
1 1
3 1
2 3
4 3
1 4

输入说明:

FJ一共有4个坐标分别为(1,1),(3,1),(2,3),(4,3)的农场。农场1和农场
4之间原本就有道路相连。

Sample Output

4.00

输出说明:

FJ选择在农场1和农场2间建一条长度为2.00的道路,在农场3和农场4间建一
条长度为2.00的道路。这样,所建道路的总长为4.00,并且这是所有方案中道路
总长最小的一种。

思路:最小生成树,先把给的边处理了,然后添加所有没有给的边作为备选边,做最小生成树。
因为算距离往写sqrt 而WA了一发。。。。蠢哭

bzoj 1601: [Usaco2008 Oct]灌水 (最小生成树)

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所需的最少代价。

Input

*第一行:一个数n

*第二行到第n+1行:第i+1行含有一个数wi

*第n+2行到第2n+1行:第n+1+i行有n个被空格分开的数,第j个数代表pij。

Output

*第一行:一个单独的数代表最小代价.

Sample Input

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output

9

输出详解:

Farmer John在第四块土地上建立水库,然后把其他的都连向那一个,这样就要花费3+2+2+2=9

思路:一开始觉得是dp…..本来打算放弃了。。。后来看到p的值,似乎一定能保证n个点相连。
那么每一个点的水源有两个来源,要么自己建,要么从别人那里来。
然后卡住了QAQ….看了题解。。
好巧妙。。因为自己建水库不好处理,我们可以假设一个源点,认为只有源点有水库,而其他点建水库的价钱认为是修一条源点到那个点的路的价钱,这样就把w[i]转化成了p[i][j]的形式。
然后包括源点在内的n+1个点,求最小生成树。