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个点,求最小生成树。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz