3771 . [模板題] Minimum Steiner Tree
TopCoder
Tags
Description
Given a connected, undirected graph with $N$ vertices and $M$ edges, where the $i$-th edge $(0 \le i < M)$ connects vertices $U_ i$ and $V_ i$ and has weight $W_ i$.
Additionally, a subset $X = \lbrace X_ 0, X_ 1, \ldots, X_ {K - 1} \rbrace$ of $V(G)$ is given. Among the subgraphs of $G$ in which the vertices in $X$ are pairwise connected, find one with the minimum sum of edge weights.
Input Format
$N$ $M$
$U_ 0$ $V_ 0$ $W_ 0$
$U_ 1$ $V_ 1$ $W_ 1$
:
$U_ {M - 1}$ $V_ {M - 1}$ $W_ {M - 1}$
$K$
$X_ 0$ $X_ 1$ ... $X_ {K - 1}$
Output Format
$Y$ $Z$
$i_ 0$ $i_ 1$ ... $i_ {Z - 1}$
$Y$ is the sum of the weights of the edges in the chosen subgraph and $Z$ is the number of chosen edges. $i_ 0, i_ 1, \ldots, i_ {Z - 1}$ are the indices of the edges in the chosen subgraph.
If there are multiple correct output, print any of them.
Sample Input 1
6 11 0 1 2 0 2 1 1 2 2 1 3 2 1 4 2 3 4 2 2 4 2 2 5 1 4 5 2 0 3 1 0 5 3 3 0 3 5
Sample Output 1
3 3 1 7 9
Sample Input 2
1 1 0 0 1 1 0
Sample Output 2
0 0
Sample Input 3
5 11 0 1 1 0 1 10 0 2 100 0 3 1000 0 4 10000 1 2 10 1 3 1 1 4 100 2 3 10 2 4 1 3 4 1 3 1 3 4
Sample Output 3
2 2 6 10
Hints
- $1 \leq N \leq 100$
- $N - 1 \leq M \leq 1000$
- $0 \leq U_ i, V_ i < N$
- $1 \leq W_ i \leq 10^ {9}$
- $1 \leq K \leq \min(N, 12)$
- $0 \le X_ 0 < X_ 1 < \ldots < X_ {K - 1} < N$
- The given graph is connected.
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|