| 题目名称 | 185. [USACO Oct08] 挖水井 |
|---|---|
| 输入输出 | water.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：368， 提交：830， 通过率：44.34% | ||||
 BaDBoY |
100 | 0.000 s | 0.00 MiB | C++ |
 河北交通广播992小强来了 |
100 | 0.000 s | 0.07 MiB | C++ |
 Ryper |
100 | 0.000 s | 1.40 MiB | C++ |
 @@@ |
100 | 0.002 s | 0.84 MiB | C++ |
 Dream |
100 | 0.003 s | 0.13 MiB | C++ |
 LGLJ |
100 | 0.004 s | 0.07 MiB | C++ |
 father |
100 | 0.004 s | 1.27 MiB | C++ |
 サイタマ |
100 | 0.005 s | 1.27 MiB | C++ |
 521 |
100 | 0.010 s | 0.39 MiB | C++ |
|
LGLJ |
100 | 0.011 s | 0.07 MiB | C++ |
| 本题关联比赛 | |||
| 图论练习和一些常规题 | |||
| 图论练习和一些常规题 | |||
| 20190521热身赛 | |||
| 关于 挖水井 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Dissolute丶Tokgo :
为什么您最后的while()换成for()就不对了呢？神奇。。。  cd
2019-05-23 16:03
19楼
| ||||
|
回复 @浮生随想 :
你上了吗  夏风
2018-10-30 10:41
18楼
| ||||
|
| ||||
|
我好水啊qwq
| ||||
|
谁可以帮我debug一下……
| ||||
|
It seems that Kruskal Algorithm isn't good at processing Full/Complete Graph. =_=
 rvalue
2017-03-03 20:53
14楼
| ||||
|
666666666666666666
| ||||
|
加一个源点即可
 dateri
2016-08-06 21:06
12楼
| ||||
|
| ||||
|
| ||||
6666
kZime
TARDIS
安呐一条小咸鱼。【题目描述】
农夫约翰决定给他的N（1<=N<=300）个牧场浇水，这些牧场被自然的命名为1..N。他可以给一个牧场引入水通过在这个牧场挖一口井或者修一条管道使这个牧场和一个已经有水的牧场连接。
在牧场i挖一口井的花费是w_i（1<=w_i<=100000）。修建一条水管连接牧场i和牧场j的花费是p_ij（1<=p_ij<=100000;p_ij=p_ji;p_ii=0）。
请确定农夫约翰为了完成浇灌所有的牧场所需的最小的总花费。
【输入格式】
第1行：一个单独的整数n。
第2..n+1行：第i+1行包含一个单独的整数w_i。
第n+2..2n+1行：第n+1+i行包含n个用空可分开的整数；其中第j个数是p_ij。
【输出格式】
第1行：一个单独的整数，表示花费。
【输入样例】
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0
【输出样例】
9
【样例说明】
这里有4个牧场，修井和修管道的代价如图。
农夫约翰可以在第4个牧场修井，并且将每个牧场和第一个连接起来，这样，花费是3+2+2+2=9。