Overview

This problem asks us to find a set of cables connecting all bases that minimizes

\[ \sum c_i + K \times \max c_i \]

In conclusion, the answer can be found by constructing a standard Minimum Spanning Tree (MST).

Analysis

First, the chosen set of cables \(S\) must connect all bases.

If \(S\) contains a cycle, the connectivity is maintained even if we remove one edge from that cycle. Furthermore, by removing an edge:

• The total cost \(\sum c_i\) decreases.
• The maximum cost \(\max c_i\) does not increase.

Therefore, the load index does not worsen.

Thus, it is sufficient to consider the optimal solution as a spanning tree consisting of exactly \(N-1\) edges.

---

Now, the problem reduces to finding a spanning tree that minimizes

\[ \text{Total Cost} + K \times \text{Maximum Edge Cost} \]

At first glance, since we need to consider both the “total cost” and the “maximum edge cost”, a standard Minimum Spanning Tree might seem insufficient.

However, the Minimum Spanning Tree has the following important property.

Minimum Spanning Tree also Minimizes the Maximum Edge Cost

A Minimum Spanning Tree not only minimizes the total cost but also minimizes the maximum edge cost used in the spanning tree.

This is known as the property of the “Minimum Bottleneck Spanning Tree”.

For example, suppose we construct an MST using Kruskal’s algorithm. Let the cost of the last selected edge be \(W\). This \(W\) is the maximum edge cost contained in that MST.

If we could connect all vertices using only edges with costs less than \(W\), Kruskal’s algorithm would have completed the spanning tree before using the edge of cost \(W\). Since it did not, any spanning tree must use at least one edge with a cost of \(W\) or greater.

In other words, the maximum edge cost of the MST is indeed the minimum possible maximum edge cost among all spanning trees.

---

Let \(T\) be the Minimum Spanning Tree and \(T'\) be any spanning tree. Then,

\[ \sum_{e \in T} c_e \leq \sum_{e \in T'} c_e \]

and

\[ \max_{e \in T} c_e \leq \max_{e \in T'} c_e \]

hold.

Also, since \(K \geq 0\), we have

\[ \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \leq \sum_{e \in T'} c_e + K \times \max_{e \in T'} c_e \]

Therefore, finding a standard Minimum Spanning Tree will yield the minimum load index.

---

A naive approach of trying all possible subsets of edges would take \(2^M\) operations, which is far too slow for the constraint \(M \leq 2 \times 10^5\).

Thus, we can efficiently construct the Minimum Spanning Tree using Kruskal’s algorithm.

Algorithm

We will use Kruskal’s algorithm.

1. Sort all edges in ascending order of their costs.
2. Prepare a Union-Find (Disjoint Set Union) data structure.
3. Process the edges in order from the smallest cost.
4. If the edge connects two different connected components, include it in the tree.
5. Add the cost of the selected edge to the total sum.
6. Update the maximum cost with the cost of the selected edge.
   • Since we process the edges in ascending order, the last selected edge will always have the maximum cost.
7. Terminate when \(N-1\) edges have been selected.
8. Output

\[ \text{Total Cost} + K \times \text{Maximum Cost} \]

as the answer.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the edges takes \(O(M \log M)\).
  • Union-Find operations take almost \(O(M)\) time.
• Space Complexity: \(O(N + M)\)
  • Storing edge information takes \(O(M)\).
  • Union-Find takes \(O(N)\).

Implementation Details

We use Union-Find to determine whether adding the current edge will form a cycle.

ru = find(u)
rv = find(v)
if ru != rv:
    # Different connected components, so select this edge

Since the edges are processed in ascending order of cost, it is sufficient to update the maximum cost of the selected edges as:

max_c = c

each time.

Also, because a spanning tree contains exactly \(N-1\) edges, we can stop the process as soon as the number of selected edges reaches \(N-1\).

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, c = map(int, input().split())
        edges.append((c, u - 1, v - 1))

    edges.sort()

    parent = list(range(N))
    size = [1] * N

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    max_c = 0
    cnt = 0

    for c, u, v in edges:
        ru = find(u)
        rv = find(v)
        if ru != rv:
            if size[ru] < size[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            size[ru] += size[rv]
            total += c
            max_c = c
            cnt += 1
            if cnt == N - 1:
                break

    print(total + K * max_c)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.