| 题目名称 | 602. 新的开始 |
|---|---|
| 输入输出 | newstart.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-09-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：144， 提交：271， 通过率：53.14% | ||||
 521 |
100 | 0.000 s | 0.00 MiB | C++ |
 NVIDIA |
100 | 0.000 s | 0.00 MiB | C++ |
 BaDBoY |
100 | 0.000 s | 0.00 MiB | C++ |
 面对疾风吧 疾风 疾风吧 |
100 | 0.003 s | 0.14 MiB | C++ |
 Dream |
100 | 0.004 s | 0.13 MiB | C++ |
 LGLJ |
100 | 0.005 s | 0.00 MiB | C++ |
 fsdh |
100 | 0.007 s | 0.95 MiB | C++ |
 zeppoe |
100 | 0.008 s | 0.68 MiB | C++ |
 SPA |
100 | 0.016 s | 0.66 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.017 s | 0.66 MiB | C++ |
| 本题关联比赛 | |||
| 练习12 | |||
| 关于 新的开始 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
%%%@天凉好个秋
为什么要建点啊，楼上大佬我不会，我好方 fsdh
2020-10-08 22:03
16楼
| ||||
|
与185挖水井 重题。
| ||||
|
| ||||
|
我好水啊qwq
| ||||
|
回复 @HouJikan :
The sister of the leading lady in Hunger Game is called Prim (23333333)  rvalue
2017-03-03 20:57
12楼
| ||||
|
是185
| ||||
|
忘了改182的文件名了。。。
Dissolute丶Tokgo
2015-10-03 08:22
10楼
| ||||
|
默默地把182的code贴了过来。。。
 devil
2015-09-14 18:21
9楼
| ||||
|
要不要这么残暴…………交了这么多回，总是跪…………
 MINE·MINE
2014-11-06 08:06
8楼
| ||||
|
原来这种题目还可以这么做，受教了= =
第一次知道prim算法的这种用法 话说prim大家是怎么读的，普利姆还是普林？ | ||||
佚名
AntiLeaf
kZime
@@@
HouJikan【题目描述】
发展采矿业当然首先得有矿井，小$FF$花了上次探险获得的千分之一的财富请人在岛上挖了 $n$ 口矿井，但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应，小 $FF$ 想到了两种办法：
1、在这一口矿井上建立一个发电站，费用为 $v$（发电站的输出功率可以供给任意多个矿井）。
2、将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 $p$。
小 $FF$ 希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
【输入格式】
第一行一个整数 $n$，表示矿井总数。
第 $2$～$n+1$ 行，每行一个整数，第 $i$ 个数 $v[i]$表示在第 $i$ 口矿井上建立发电站的费用。
接下来为一个 $n*n$ 的矩阵 $P$，其中 $p[ i , j ]$表示在第 $i$ 口矿井和第 $j$ 口矿井之间建立
电网的费用（数据保证有 $p[ i, j ] = p[ j, i ]$, 且 $p[ i, i ]=0$）。
【输出格式】
仅一个整数，表示让所有矿井获得充足电能的最小花费。
【输入样例】
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0
【输出样例】
9
【提示】
小 $FF$ 可以选择在$4$号矿井建立发电站然后把所有矿井都与其建立电网，总花费是 $3+2+2+2 = 9$。
【数据范围】
对于$30$%的数据：$1<=n<=50$;
对于$100$%的数据：$1<=n<=300; 0<=v[i], p[i,j] <=10^5$.