Overview

Given \(N\) servers to be connected by a spanning tree, the problem asks to minimize the total installation cost while necessarily including \(K\) specified cables. If no spanning tree containing all specified cables exists, output \(-1\).

Analysis

Key Insight

This problem is about finding a “minimum spanning tree where some edges are forced to be selected.”

A standard minimum spanning tree (MST) can be found using Kruskal’s algorithm, which works by “considering edges in increasing order of cost and adopting those that do not form a cycle.”

The crucial observation here is that we can first add all mandatory edges, and then run Kruskal’s algorithm on the remaining edges.

Why This Is Correct

Consider the state after adding all mandatory edges. The connected components are managed by a Union-Find structure, forming several “groups.” What remains is to connect all these groups into one. This reduces exactly to the minimum spanning tree problem on the graph contracted by the mandatory edges. Therefore, it is optimal to greedily adopt edges that connect different connected components by examining the remaining edges in order of cost (Kruskal’s algorithm).

Impossible Cases

The answer is \(-1\) in the following two cases:

1. The mandatory edges form a cycle: While adding the \(K\) mandatory edges, if an edge appears that connects two vertices already in the same connected component, it is impossible to form a spanning tree (which must be cycle-free).
2. The spanning tree cannot be completed: Even combining mandatory edges and additional edges, if the total is fewer than \(N-1\) edges (the overall graph is disconnected).

Algorithm

1. Read the input and manage the set of mandatory edges.
2. Initialize a Union-Find structure (\(N\) vertices).
3. Add all mandatory edges. If both endpoints are already in the same connected component when adding an edge, a cycle would form, so output \(-1\) and terminate. Accumulate the cost.
4. Sort the non-mandatory edges in ascending order of cost.
5. Run Kruskal’s algorithm: examine non-mandatory edges in increasing order and adopt those that connect different connected components. Stop when the total number of adopted edges reaches \(N-1\).
6. If \(N-1\) edges have been selected in total, output the total cost; otherwise, output \(-1\).

Concrete Example

\(N=4\), with edges \((1,2,10), (2,3,5), (3,4,3), (1,4,1)\) between servers, and edge \((1,2,10)\) is mandatory:

• First, add edge \((1,2,10)\) → \(\{1,2\}, \{3\}, \{4\}\)
• Remaining edges sorted by cost: \((1,4,1), (3,4,3), (2,3,5)\)
• Adopt \((1,4,1)\) → \(\{1,2,4\}, \{3\}\)
• Adopt \((3,4,3)\) → \(\{1,2,3,4\}\) → Complete!
• Total cost: \(10 + 1 + 3 = 14\)

Complexity

• Time complexity: \(O(M \log M)\) (sorting non-mandatory edges is the bottleneck. Union-Find operations are nearly \(O(\alpha(N))\), essentially constant)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Use Union-Find with path compression and union by rank to perform union/find operations efficiently.

• Manage the set of mandatory edges using a set to determine in \(O(1)\) whether an edge is mandatory.

• Edge indices are 1-indexed in the problem statement but should be converted to 0-indexed internally.

• When \(K = 0\), the final line (mandatory edge list) does not exist, so special handling is needed in input processing.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    edges = []
    for i in range(M):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))
    
    required = set()
    if K > 0:
        es = list(map(int, input().split()))
        for e in es:
            required.add(e - 1)  # 0-indexed
    
    # Union-Find
    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True
    
    total_cost = 0
    
    # Step 1: Add all required edges
    for idx in required:
        u, v, w = edges[idx]
        if not union(u, v):
            # Required edges form a cycle -> impossible
            print(-1)
            return
        total_cost += w
    
    # Step 2: Check if required edges alone don't disconnect things that can't be fixed
    # Now do Kruskal on remaining edges to complete the spanning tree
    # Sort non-required edges by weight
    non_required = []
    for i in range(M):
        if i not in required:
            non_required.append((edges[i][2], edges[i][0], edges[i][1]))
    
    non_required.sort()
    
    edges_used = K
    
    for w, u, v in non_required:
        if edges_used == N - 1:
            break
        if union(u, v):
            total_cost += w
            edges_used += 1
    
    if edges_used == N - 1:
        print(total_cost)
    else:
        print(-1)

main()

---

This editorial was generated by claude4.6opus-thinking.