切断公路
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
切断公路
题目背景
题目描述
小明在玩一款攻占城池的游戏,现在敌国拥有座城池,有条公路将这些城池连接成一个整体,每个城市都有驻扎军队,第座城市的兵力为。
小明注意到,城池之间会利用这些公路来运输粮草等补给,所以要攻占一座城就要切断这座城和其他城的连接。但是小明的野心很大,他想把这条公路全部切断,准备一口气攻下这座城池。为了防止敌人重新打通这些公路,小明需要派遣足够的兵力去切断这些通路,需要的兵力至少是当前这条公路连接的两个连通块中,每个连通块的城池拥有的最大兵力之和。
小明有一个好消息和一个坏消息。坏消息是,已经派出去的兵力不能再次调动。好消息是,已经切断的公路不会重新被连通,因此他在切断某条公路之后,切断其他公路需要的兵力可能会更少。
小明意识到,不同的切割公路的顺序,所需要的总兵力不一定相同,所以他找到了你,想请你帮他计算,要切断所有条公路,最少需要花费的总兵力是多少?
输入格式
第一行一个正整数表示城池数量。
第二行个正整数表示每个城池的兵力。
接下来行每行两个正整数表示城池和有公路连接。
输出格式
一个正整数表示小明需要派出的最小兵力。
样例 #1
样例输入 #1
3
1 2 3
1 2
2 3
样例输出 #1
8
提示
样例解释1:
先切断2到3的公路,此时城池被分成(1,2)和(3)两个连通块,第一个连通块的城池最大兵力是2,第二个连通块的城池最大兵力是3,所需兵力为2+3=5;再切断1到2的公路,将(1,2)分成(1)和(2)两个部分,所需兵力为1+2=3(因为城池3的兵力到不了这个连通块,所以不用管),因此所需的最小兵力总共是8。
如果先切断1到2的公路,此时城池被分成(1)和(2,3)两个连通块,第一个连通块的城池最大兵力是1,第二个连通块的城池最大兵力是3,所需兵力为1+3=4;再切断2到3的公路,所需兵力为2+3=5,总兵力为9,不是最小兵力。
数据范围
对的数据,。
对的数据,。
对另外的数据,对任意,号点和号点相连。
对的数据,。
国庆集训S组模拟赛1
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2023-10-5 9:00
- End at
- 2023-10-5 17:00
- Duration
- 4 hour(s)
- Host
- Partic.
- 51