Summary

This problem asks us to find a set of cables that connects all bases while minimizing the “total cost + \(K \times\) maximum cost”. In fact, this can be solved simply by finding the Minimum Spanning Tree (MST).

Analysis

The Chosen Set of Edges Can Be a “Spanning Tree”

First, if the chosen set of cables \(S\) contains a cycle, it is redundant. Removing one edge from the cycle maintains connectivity while strictly decreasing the total cost, and the maximum cost will not increase. In other words, the load index (the objective function) will not increase.

Therefore, the optimal \(S\) will always be a “spanning tree” (which connects all bases with \(N-1\) edges).

Which Spanning Tree to Choose

The load index consists of the following two terms:

\[ \underbrace{\sum_{i \in S} c_i}_{\text{total cost}} \;+\; K \times \underbrace{\max_{i \in S} c_i}_{\text{maximum cost}} \]

At first glance, it seems we need to consider the trade-off between the “total cost” and the “maximum cost”, and adjust which one to prioritize depending on the value of \(K\). However, there is an important property here:

A Minimum Spanning Tree (MST) minimizes the total cost and, at the same time, minimizes the maximum cost of the edges it contains.

This is a well-known property: an MST is also a “minimum bottleneck spanning tree”. In other words, if we find an MST, both:

• Total cost \(\sum c_i\) \(\to\) minimum among all spanning trees
• Maximum cost \(\max c_i\) \(\to\) minimum among all spanning trees

are achieved simultaneously.

Since both terms are minimized simultaneously, the load index (their sum) will also be minimized by the MST for any value of \(K \geq 0\). Therefore, we do not need to split into cases based on the value of \(K\); we can simply find any MST.

Algorithm

We construct the MST using Kruskal’s algorithm.

1. Sort all edges in ascending order of their cost \(c\).
2. Iterate through the edges starting from the one with the smallest cost. If the endpoints of the edge are not yet connected, add this edge to the MST (use a Union-Find tree to check connectivity).
3. Keep track of the total cost by adding the cost of each chosen edge. Since we process edges in ascending order of cost, the cost of the last added edge will be the maximum cost in the MST.
4. Stop when we have chosen \(N-1\) edges.

Finally, output “total cost + \(K \times\) maximum cost”.

As a concrete example, if the MST consists of edges with costs \(1, 2, 5\), the total cost is \(1+2+5=8\), and the maximum cost is \(5\). If \(K=3\), the load index is \(8 + 3 \times 5 = 23\).

Complexity

• Time Complexity: \(O(M \log M)\) (dominated by sorting the edges; Union-Find operations are practically constant time)
• Space Complexity: \(O(N + M)\)

Implementation Points

• By representing edges as tuples (c, u, v) and sorting them, they can be easily sorted in ascending order of their costs.

• Since we process edges in ascending order of cost, updating mx = c every time we add an edge to the MST ensures that mx will automatically hold the maximum cost in the MST when the loop ends (no need to compute max separately).

• Use path compression in the Union-Find data structure to speed it up.

• Since \(N\) and \(M\) can be as large as \(2 \times 10^5\), reading all inputs at once using sys.stdin.buffer.read() is fast in Python.

• Although the answer fits within a 64-bit integer even when \(K\) and \(c\) are large, Python handles arbitrarily large integers, so there is no need to worry about overflow.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    edges = []
    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); c = int(data[idx+2]); idx += 3
        edges.append((c, u, v))
    edges.sort()

    parent = list(range(N + 1))

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

    total = 0
    mx = 0
    cnt = 0
    for c, u, v in edges:
        ru = find(u)
        rv = find(v)
        if ru != rv:
            parent[ru] = rv
            total += c
            mx = c  # 昇順処理なので最後に採用した辺が最大辺
            cnt += 1
            if cnt == N - 1:
                break

    print(total + K * mx)

main()

---

This editorial was generated by claude4.8opus-high.