K - Network Installation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君はある地域の通信ネットワークの整備を担当しています。この地域には N 個の拠点があり、拠点同士を結ぶことができる M 本の候補回線が存在します。各候補回線 i（1 \leq i \leq M）は拠点 U_i と拠点 V_i を双方向に結び、敷設コストとして W_i 円がかかります。

予算の都合上、全ての拠点にサービスを提供することはできません。そこで高橋君は、N 個の拠点の中から ちょうど K 個の拠点 を選んでサービス対象とし、それら K 個の拠点が全て互いに（直接または間接的に）通信できるように回線を敷設したいと考えています。

具体的には、候補回線の中からいくつかを選んで敷設し、敷設した回線のみを使って、選んだ K 個の拠点のうち任意の 2 つの間で通信が可能であるようにします。なお、敷設した回線による通信経路の途中に、サービス対象として選んだ K 個に含まれない拠点が中継地点として含まれていても構いません（中継のための追加費用はかかりません）。拠点の選択自体にもコストはかからず、費用として考慮するのは敷設した回線のコストの合計のみです。

高橋君が K 個の拠点を最適に選び、それらを連結にするために敷設する回線のコストの合計を最小化するとき、その最小値を求めてください。

より形式的に述べます。N 個の拠点を頂点 1, 2, \ldots, N とし、M 本の候補回線を辺とする重み付き無向グラフ G を考えます。頂点集合 \{1, 2, \ldots, N\} から大きさ K の部分集合 S（|S| = K）を選びます。次に、M 本の辺の集合から部分集合 T を選びます。このとき、全頂点 \{1, 2, \ldots, N\} と辺集合 T からなるグラフにおいて、S に含まれる任意の 2 頂点間にパスが存在することを要求します。この条件を満たすすべての (S, T) の組にわたって、T に含まれる辺の重みの合計の最小値を求めてください。

制約

  • 2 \leq N \leq 300
  • 1 \leq M \leq \dfrac{N(N-1)}{2}
  • 2 \leq K \leq \min(N, 5)
  • K = 5 の場合、N \leq 80
  • 1 \leq U_i < V_i \leq N
  • 1 \leq W_i \leq 10^6
  • 候補回線に重複はない（すなわち、i \neq j ならば (U_i, V_i) \neq (U_j, V_j)）
  • 条件を満たす (S, T) の組が少なくとも 1 つ存在する
  • 入力は全て整数である

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、拠点の数 N、候補回線の数 M、選ぶ拠点の数 K がスペース区切りで与えられる。
  • 続く M 行のうち i 行目（1 \leq i \leq M）には、候補回線 i が結ぶ 2 つの拠点 U_i, V_i および敷設コスト W_i がスペース区切りで与えられる。

出力

K 個の拠点の選び方および回線の敷設方法を最適にしたときの、敷設コストの合計の最小値を 1 行で出力せよ。

入力例 1

4 4 3
1 2 3
2 3 4
3 4 5
1 4 10

出力例 1

7

入力例 2

5 3 3
1 2 1
2 3 1
4 5 1

出力例 2

2

入力例 3

10 17 4
1 2 7
1 3 2
2 3 5
2 4 10
3 5 4
4 5 3
4 6 8
5 6 6
5 7 9
6 8 1
7 8 2
7 9 11
8 9 4
8 10 7
9 10 3
1 10 20
3 8 12

出力例 3

7

入力例 4

25 50 5
1 2 8
1 3 15
2 3 4
2 4 12
3 5 7
4 5 6
4 6 20
5 6 5
5 7 9
6 8 3
7 8 11
7 9 14
8 10 2
9 10 10
9 11 6
10 12 8
11 12 4
11 13 13
12 14 5
13 14 7
13 15 9
14 16 3
15 16 12
15 17 6
16 18 4
17 18 8
17 19 15
18 20 5
19 20 7
19 21 10
20 22 6
21 22 4
21 23 11
22 24 3
23 24 8
23 25 14
24 25 2
1 25 100
3 10 18
6 13 17
8 15 16
10 17 19
12 19 21
14 21 18
16 23 20
2 9 22
4 11 24
7 14 23
11 18 22
18 25 13

出力例 4

15

入力例 5

2 1 2
1 2 1000000

出力例 5

1000000

Score : 466 pts

Problem Statement

Takahashi is in charge of setting up a communication network in a certain region. There are N bases in this region, and there are M candidate lines that can connect them. Each candidate line i (1 \leq i \leq M) bidirectionally connects base U_i and base V_i, costing W_i yen to install.

Due to budget constraints, it is not possible to provide services to all bases. Therefore, Takahashi wants to choose exactly K bases out of the N bases to be the service targets, and install lines so that all of these K bases can communicate with each other (directly or indirectly).

Specifically, he will choose and install some of the candidate lines, ensuring that any two of the selected K bases can communicate using only the installed lines. Note that the communication path between the selected K bases may include bases not in the selected K as intermediate relay points (no additional cost is incurred for relaying). There is no cost for choosing the bases themselves; the only cost to consider is the sum of the installation costs of the selected lines.

Find the minimum total cost of the installed lines when Takahashi optimally chooses K bases and installs lines to make them connected.

More formally, consider a weighted undirected graph G with N vertices 1, 2, \ldots, N representing the bases, and M edges representing the candidate lines. We choose a subset S of size K (|S| = K) from the vertex set \{1, 2, \ldots, N\}. Next, we choose a subset T from the set of M edges. We require that in the graph consisting of all vertices \{1, 2, \ldots, N\} and the edge set T, there exists a path between any two vertices in S. Find the minimum total weight of the edges in T over all pairs (S, T) that satisfy this condition.

Constraints

  • 2 \leq N \leq 300
  • 1 \leq M \leq \dfrac{N(N-1)}{2}
  • 2 \leq K \leq \min(N, 5)
  • If K = 5, then N \leq 80
  • 1 \leq U_i < V_i \leq N
  • 1 \leq W_i \leq 10^6
  • There are no duplicate candidate lines (i.e., if i \neq j, then (U_i, V_i) \neq (U_j, V_j)).
  • There is at least one pair (S, T) that satisfies the condition.
  • All input values are integers.

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of bases N, the number of candidate lines M, and the number of bases to choose K, separated by spaces.
  • The i-th of the following M lines (1 \leq i \leq M) contains the two bases U_i and V_i connected by candidate line i, and its installation cost W_i, separated by spaces.

Output

Print the minimum total installation cost when the choice of K bases and the line installation are optimized, in a single line.

Sample Input 1

4 4 3
1 2 3
2 3 4
3 4 5
1 4 10

Sample Output 1

7

Sample Input 2

5 3 3
1 2 1
2 3 1
4 5 1

Sample Output 2

2

Sample Input 3

10 17 4
1 2 7
1 3 2
2 3 5
2 4 10
3 5 4
4 5 3
4 6 8
5 6 6
5 7 9
6 8 1
7 8 2
7 9 11
8 9 4
8 10 7
9 10 3
1 10 20
3 8 12

Sample Output 3

7

Sample Input 4

25 50 5
1 2 8
1 3 15
2 3 4
2 4 12
3 5 7
4 5 6
4 6 20
5 6 5
5 7 9
6 8 3
7 8 11
7 9 14
8 10 2
9 10 10
9 11 6
10 12 8
11 12 4
11 13 13
12 14 5
13 14 7
13 15 9
14 16 3
15 16 12
15 17 6
16 18 4
17 18 8
17 19 15
18 20 5
19 20 7
19 21 10
20 22 6
21 22 4
21 23 11
22 24 3
23 24 8
23 25 14
24 25 2
1 25 100
3 10 18
6 13 17
8 15 16
10 17 19
12 19 21
14 21 18
16 23 20
2 9 22
4 11 24
7 14 23
11 18 22
18 25 13

Sample Output 4

15

Sample Input 5

2 1 2
1 2 1000000

Sample Output 5

1000000