#\. Erasing Vertices 2
Erasing Vertices 2
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.
题面翻译
有一个有 个顶点 条边的无向图，每个点有一个点权 , 现在你需要进行以下操作 次：
- 选择一个 未被删除 的点
- 将这个点及其相连的边删除，代价为与它所有 直接相连 的 未被删除的 的点的点权之和
现在请你求出删除整个无向图，单次操作代价最大值的最小值。
Translated by Microchip2333
题目描述
頂点 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。 本目の辺は頂点 と頂点 を結んでいます。頂点 には正整数 が書かれています。
あなたは、以下の操作を 回繰り返します。
- まだ削除されていない頂点 を選び、「頂点 」と「頂点 を端点に持つ辺全て」を削除する。この操作のコストは、頂点 と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。
回の操作全体のコストを、 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
4 3
3 1 4 2
1 2
1 3
4 1
样例输出 #1
3
样例 #2
样例输入 #2
7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7
样例输出 #2
1199
提示
制約
- 与えられるグラフは単純。
- 入力は全て整数。
Sample Explanation 1
以下のように操作を行うことにより、 回の操作のコストのうちの最大値を にすることができます。 - 頂点 を選ぶ。コストは である。 - 頂点 を選ぶ。コストは である。 - 頂点 を選ぶ。コストは である。 - 頂点 を選ぶ。コストは である。 回の操作のコストのうちの最大値を 以下にすることはできないため、解は です。
北辰OI提高组第2周序列问题课后练习题👍
- Status
- Done
- Rule
- IOI
- Problem
- 44
- Start at
- 2024-1-7 16:00
- End at
- 2024-2-18 8:00
- Duration
- 1000 hour(s)
- Host
-
yuyongchao
- Partic.
- 15
