/
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
ある地域には N 個の都市があり、それぞれ 1 から N の番号が付けられています。都市の間には M 本の通信ケーブルが敷設されており、各ケーブルは双方向に通信可能です。 i 番目のケーブル (1 \leq i \leq M) は都市 U_i と都市 V_i を結んでおり、その維持コストは正整数 W_i です。グラフに自己ループや多重辺は存在しません。
このグラフは 2-辺連結です。すなわち、M 本のケーブルのうちどの 1 本を取り除いても、残りのケーブルで任意の 2 つの都市間の通信が可能です。
高橋君はこの地域の通信管理者で、ケーブルの中からちょうど N - 1 本を選び、すべての都市を連結にする「基幹ネットワーク」を構築しようとしています。このような N - 1 本のケーブルの選び方は全域木に対応します。高橋君は、基幹ネットワークに含まれるケーブルの維持コストの合計ができるだけ小さくなるようにケーブルを選びます。すなわち、高橋君は最小全域木を構築します。
一方、青木君はライバル企業のエンジニアです。青木君は高橋君が基幹ネットワークを構築する前に、M 本のケーブルの中からちょうど 1 本を選んで切断することができます。切断されたケーブルは使用不能となり、基幹ネットワークに含めることができなくなります。グラフが 2-辺連結であるため、どのケーブルが切断されても、残りの M - 1 本のケーブルで全域木を構築できることが保証されます。
このゲームの流れは以下の通りです。
- 青木君が M 本のケーブルの中からちょうど 1 本を選んで切断する。
- 高橋君が残りの M - 1 本のケーブルの中から N - 1 本を選び、維持コストの合計が最小となる全域木(最小全域木)を構築する。
青木君は、高橋君が最小全域木を構築することを見越した上で、その維持コストの合計が最大となるように切断するケーブルを選びます。
なお、最小全域木が複数存在する場合でも、その維持コストの合計は一意に定まります。したがって、青木君がどのケーブルを切断するかが決まれば、高橋君が構築する基幹ネットワークの維持コストの合計も一意に定まります。
青木君が最適に妨害し、高橋君が最適にネットワークを構築したとき、基幹ネットワークの維持コストの合計を求めてください。
制約
- 3 \leq N \leq 10^5
- N \leq M \leq 2 \times 10^5
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i(自己ループは存在しない)
- i \neq j ならば (U_i, V_i) \neq (U_j, V_j) かつ (U_i, V_i) \neq (V_j, U_j)(多重辺は存在しない)
- 1 \leq W_i \leq 10^9
- W_i は整数である
- グラフは 2-辺連結である(任意の 1 本の辺を取り除いてもグラフは連結である)
- 答えは 2 \times 10^{14} 以下であることが保証される
入力
N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 1 行目には、都市の数を表す整数 N と、ケーブルの数を表す整数 M が、スペース区切りで与えられる。
- 2 行目から M + 1 行目では、各ケーブルの情報が M 行で与えられる。
- 1 + i 行目 (1 \leq i \leq M) では、 i 番目のケーブルが結ぶ都市の番号 U_i , V_i と、その維持コスト W_i がスペース区切りで与えられる。
出力
青木君が最適に 1 本のケーブルを切断し、高橋君が残りのケーブルから維持コストの合計が最小となるように基幹ネットワークを構築したとき、その維持コストの合計を整数として 1 行で出力せよ。
入力例 1
3 3 1 2 1 2 3 2 1 3 3
出力例 1
5
入力例 2
4 5 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5
出力例 2
9
入力例 3
6 9 1 2 3 2 3 5 3 4 2 4 5 7 5 6 1 6 1 4 1 3 8 2 5 6 4 6 9
出力例 3
20
入力例 4
8 12 1 2 10 2 3 20 3 4 30 4 5 40 5 6 50 6 7 60 7 8 70 8 1 80 1 5 15 2 6 25 3 7 35 4 8 45
出力例 4
210
入力例 5
3 3 1 2 1000000000 2 3 1000000000 1 3 1000000000
出力例 5
2000000000
Score : 466 pts
Problem Statement
There are N cities in a region, numbered from 1 to N. Between the cities, M communication cables have been laid, and each cable allows bidirectional communication. The i-th cable (1 \leq i \leq M) connects city U_i and city V_i, and its maintenance cost is a positive integer W_i. The graph contains no self-loops or multiple edges.
This graph is 2-edge-connected. That is, even if any single cable among the M cables is removed, communication between any two cities remains possible using the remaining cables.
Takahashi is the communication administrator of this region and is trying to build a "backbone network" by selecting exactly N - 1 cables that connect all cities. Such a selection of N - 1 cables corresponds to a spanning tree. Takahashi selects cables so that the total maintenance cost of the cables included in the backbone network is as small as possible. In other words, Takahashi constructs a minimum spanning tree.
On the other hand, Aoki is an engineer from a rival company. Before Takahashi constructs the backbone network, Aoki can choose exactly 1 cable from the M cables and cut it. A cut cable becomes unusable and cannot be included in the backbone network. Since the graph is 2-edge-connected, it is guaranteed that no matter which cable is cut, a spanning tree can still be constructed from the remaining M - 1 cables.
The flow of this game is as follows:
- Aoki chooses exactly 1 cable from the M cables and cuts it.
- Takahashi selects N - 1 cables from the remaining M - 1 cables and constructs a spanning tree with the minimum total maintenance cost (minimum spanning tree).
Aoki chooses which cable to cut so as to maximize the total maintenance cost, anticipating that Takahashi will construct a minimum spanning tree.
Note that even if multiple minimum spanning trees exist, their total maintenance cost is uniquely determined. Therefore, once Aoki decides which cable to cut, the total maintenance cost of the backbone network Takahashi constructs is also uniquely determined.
Find the total maintenance cost of the backbone network when Aoki sabotages optimally and Takahashi constructs the network optimally.
Constraints
- 3 \leq N \leq 10^5
- N \leq M \leq 2 \times 10^5
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i (no self-loops)
- If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j) (no multiple edges)
- 1 \leq W_i \leq 10^9
- W_i is an integer
- The graph is 2-edge-connected (the graph remains connected after removing any single edge)
- It is guaranteed that the answer is at most 2 \times 10^{14}
Input
N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- The first line contains an integer N representing the number of cities and an integer M representing the number of cables, separated by a space.
- From the 2nd line to the (M + 1)-th line, information about each cable is given over M lines.
- The (1 + i)-th line (1 \leq i \leq M) contains the city numbers U_i, V_i that the i-th cable connects, and its maintenance cost W_i, separated by spaces.
Output
Output in a single line, as an integer, the total maintenance cost of the backbone network when Aoki optimally cuts one cable and Takahashi constructs the backbone network to minimize the total maintenance cost from the remaining cables.
Sample Input 1
3 3 1 2 1 2 3 2 1 3 3
Sample Output 1
5
Sample Input 2
4 5 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5
Sample Output 2
9
Sample Input 3
6 9 1 2 3 2 3 5 3 4 2 4 5 7 5 6 1 6 1 4 1 3 8 2 5 6 4 6 9
Sample Output 3
20
Sample Input 4
8 12 1 2 10 2 3 20 3 4 30 4 5 40 5 6 50 6 7 60 7 8 70 8 1 80 1 5 15 2 6 25 3 7 35 4 8 45
Sample Output 4
210
Sample Input 5
3 3 1 2 1000000000 2 3 1000000000 1 3 1000000000
Sample Output 5
2000000000