Overview

This is a problem of constructing a network (minimum spanning tree) that minimizes communication cost, under the constraint that certain required cables (edges) must be included.

Analysis

The problem of constructing a network that connects all servers without forming cycles is known in graph theory as finding a “Minimum Spanning Tree (MST).” A well-known algorithm for finding the MST is Kruskal’s algorithm.

In the standard Kruskal’s algorithm, all edges are sorted in ascending order of cost, and a greedy approach is used to “add edges one by one while avoiding cycles.”

However, in this problem, \(K\) cables are specified as “must be included.” The key point is how to handle this. Intuitively, the approach of “connecting all \(K\) required cables first, then filling in the remaining gaps with the lowest-cost cables” comes to mind. In fact, this method correctly finds the minimum cost.

Note that in the following cases, a spanning tree cannot be constructed, so -1 must be output: 1. When the \(K\) required cables alone form a cycle This violates the condition that a spanning tree must not contain cycles, making construction impossible. 2. When all available cables are used but still cannot connect all servers If the total number of selected cables is less than \(N-1\), the entire set of servers is not connected.

Algorithm

For cycle detection and connectivity checking of vertices, we use Union-Find (Disjoint Set Union data structure).

1. Initialize a Union-Find with \(N\) vertices.
2. First, examine the \(K\) required cables in order and connect the servers using Union-Find (unite operation).
   • At this point, if the two servers being connected already belong to the same group (= a cycle would be formed), determine that construction is impossible, output -1, and terminate.
   • If no cycle is formed, add the cable’s cost to the total and increment the count of used cables by \(+1\).
3. Next, sort the remaining non-required cables in ascending order of installation cost \(W_i\).
4. Examine the sorted cables in order, checking with Union-Find whether adding each would form a cycle.
   • Only when no cycle would be formed (i.e., the servers to be connected belong to different groups), adopt the cable, add its cost to the total, and increment the count by \(+1\).
   • Once the number of used cables reaches \(N-1\), the spanning tree is complete, so stop the search.
5. Finally, if the number of used cables is exactly \(N-1\), output the total cost; otherwise (since the entire graph is not connected), output -1.

Complexity

• Time complexity: \(O(M \log M)\)
  • Sorting the non-required edges takes \(O(M \log M)\) time.
  • Each Union-Find operation is extremely fast (inverse Ackermann function \(\alpha(N)\)), so the total edge addition processing takes \(O(M \alpha(N))\).
  • Therefore, the overall time complexity is dominated by the sorting step, yielding \(O(M \log M)\).
• Space complexity: \(O(N + M)\)
  • The Union-Find arrays use \(O(N)\) memory, and the lists or sets holding edge information use \(O(M)\) memory.

Implementation Notes

• 1-indexed to 0-indexed conversion: The server numbers and cable numbers in the input start from \(1\), but handling them as \(0\)-indexed within arrays and Union-Find in the program simplifies the implementation.

• Fast lookup for required cables: To determine whether a given cable is required, storing the required cable numbers in a set (hash table) allows \(O(1)\) fast lookup.

• Increasing recursion limit (Python-specific): Since the find function of Union-Find uses recursive calls, in Python you need to increase the recursion depth limit using sys.setrecursionlimit (to handle the constraint \(N = 2 \times 10^5\)).

• Fast I/O: Since the input volume is large, reading all input at once using sys.stdin.read().split() can significantly reduce execution time.

  Source Code

import sys

sys.setrecursionlimit(300000)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    U = [0] * M
    V = [0] * M
    W = [0] * M
    
    idx = 3
    for i in range(M):
        U[i] = int(input_data[idx]) - 1
        V[i] = int(input_data[idx+1]) - 1
        W[i] = int(input_data[idx+2])
        idx += 3
        
    E = set()
    if K > 0:
        for _ in range(K):
            E.add(int(input_data[idx]) - 1)
            idx += 1
            
    uf = UnionFind(N)
    total_cost = 0
    edge_count = 0
    
    for i in E:
        u, v, w = U[i], V[i], W[i]
        if not uf.unite(u, v):
            print(-1)
            return
        total_cost += w
        edge_count += 1
        
    other_edges = []
    for i in range(M):
        if i not in E:
            other_edges.append((W[i], U[i], V[i]))
            
    other_edges.sort()
    
    for w, u, v in other_edges:
        if edge_count == N - 1:
            break
        if uf.unite(u, v):
            total_cost += w
            edge_count += 1
            
    if edge_count == N - 1:
        print(total_cost)
    else:
        print(-1)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.