| 题目名称 | 1002. [WZOI 2011 S3] 周年纪念日 |
|---|---|
| 输入输出 | anniversary.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：8， 通过率：37.5% | ||||
 LCWhiStLe |
100 | 0.365 s | 7.25 MiB | C++ |
 Hale |
100 | 0.450 s | 47.23 MiB | C++ |
 再见 |
100 | 1.109 s | 5.49 MiB | C++ |
|
LCWhiStLe |
70 | 0.298 s | 8.16 MiB | C++ |
|
LCWhiStLe |
50 | 0.373 s | 6.34 MiB | C++ |
 Makazeu |
30 | 7.124 s | 6.80 MiB | C++ |
|
LCWhiStLe |
0 | 0.370 s | 6.64 MiB | C++ |
|
Hale |
0 | 1.130 s | 26.63 MiB | C++ |
| 本题关联比赛 | |||
| 20120809 | |||
| 关于 周年纪念日 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
边没有枚举到m导致没有一遍A，真是ZZ
退役预定 | ||||
|
辣鸡极大值毁我青春
极大值开到 5*1e18才过。。。 LCWhiStLe
2017-09-11 15:30
1楼
| ||||
Problem 3 周年纪念日
(anniversary.pas/c/cpp)
背景
WZland即将迎来一个举国欢庆的日子—建国150亿周年纪念日，值此之际WZland有许多事情要准备……问题描述
WZland的国王决定举办一个晚会，这次晚会要求所有的WZland居民都参加，但是他发现WZland的所有城市之间的道路都已经毁坏（平时WZland的居民都在自己的城市里活动，所以他们对于那些道路一点都不关心）。这是一件十分麻烦的事情，因为这个晚会要求所有居民都来参加，于是国王决定要重建道路。他找出了WZland的地图，他发现WZland有N个城市，有M条破败的双向道路连接着这N个城市。由于周年纪念日就要到来，为了节省时间国王决定修建的道路恰好将这N个城市连接起来。修建一条长度为L的道路，需要花费L个Ws(Ws是WZland的通用货币)，国王想要将总的花费降到最少，这样他能有足够多的钱来举办晚会。国王还有一个要求，因为这些道路是同时开始修建的，因此修建完这些道路的总时间等于修建完最长的那条道路的时间（你可以认为所有工人的修建速度是一样的，即一单位时间修建1单位长度的道路），国王想要总的修建时间最少。
由于要举行晚会，国王需要找到一个地点来举办晚会，这同样是一件十分麻烦的事情。因为WZland的每个人都十分懒，他们不愿意多走路（就连在这周年纪念日也不例外）。WZland的居民每走1单位长度的路就会产生1单位的不高兴度（这就是为什么他们都不愿离开自己城市的原因）。WZland的国王想要这个晚会的不高兴度尽量低（晚会的不高兴度就等于所有参加晚会的人的不高兴度的和），这就要求选取一个合适的地点来举办晚会（WZland的居民要通过即将修建好的道路，来到这个晚会举办地）。
举个例子，如果晚会在城市u举行，城市i有Pi个人，城市u和城市i的距离为D(u,i)，那么这些人产生的不高兴度之和为Pi*D(u,i)。
国王把这个任务交给了你，他希望你能找出一个地点，是所有人的不高兴度之和最小。
输入格式
第2行到N+1行：第i+1行包含一个整数Pi，表示城市i的居民人数。
第N+2行到N+M+1行，每行三个整数A，B，L(1≤A,B≤N，A≠B)，表示A和B之间有一条长度为L的破坏道路。
注意：两个城市之间可能会有多条道路。
输出格式
第一行两个整数C，T(用一个空格隔开)，表示修建道路的最少花费和最少时间。
第二行两个整数U，H(用一个空格隔开)，表示晚会的地点(如果有多个地点满足条件，输出编号最小的那个城市)和相应地点所有人的不高兴度之和。
样例输入输出
5 7
3
2
2
1
4
1 5 1
1 3 7
2 1 4
2 3 6
3 4 5
2 4 3
5 4 2
anniversary.out
11 5
5 29
样例解释
合法的修建方案如下图(相邻城市之间的距离和每个城市的人数见样例)：
