Overview

This problem asks us to find a set of edges (a spanning tree) that connects all vertices in a given undirected graph with \(N\) vertices and \(M\) edges, such that the “load index” (the sum of the total cost and \(K\) times the maximum cost of the selected edges) is minimized.

Analysis

At first glance, it might seem like there is a trade-off where we sacrifice the total cost to suppress the maximum cost. However, in fact, we can minimize the load index simply by finding a standard Minimum Spanning Tree (MST).

Let’s consider the reason based on the formula for the load index: \(\sum_{i \in S} c_i + K \times \max_{i \in S} c_i\).

1. Minimality of the maximum cost (Bottleneck Spanning Tree) Among all spanning trees that connect the graph, one that minimizes the maximum cost of its edges is called a “Bottleneck Spanning Tree.” An important property in graph theory is that a Minimum Spanning Tree (MST) is always also a bottleneck spanning tree. In other words, no matter which spanning tree we choose, we cannot make its maximum cost strictly less than the maximum cost of the MST (let this be \(M_{mst}\)).

2. Minimality of the total cost By definition, the MST minimizes the total cost \(\sum_{i \in S} c_i\) among all spanning trees.

3. Compatibility of both Suppose we choose a spanning tree \(S'\) whose maximum cost is strictly greater than \(M_{mst}\). In this case:

   • The maximum cost term \(K \times \max_{i \in S'} c_i\) will be greater than or equal to \(K \times M_{mst}\) in the MST.
   • The total cost term \(\sum_{i \in S'} c_i\) will also be greater than or equal to the total cost of the MST.

Therefore, even if we make the maximum cost larger than that of the MST, neither term of the load index will improve (decrease). Also, it is impossible to make the maximum cost less than \(M_{mst}\).

From the above, we can see that the set of edges forming a standard Minimum Spanning Tree always minimizes the load index.

Algorithm

We will use Kruskal’s algorithm, which is a representative method for finding a minimum spanning tree.

1. Sort all edges in ascending order of their cost \(c_i\).
2. Prepare a Union-Find (DSU) data structure to efficiently manage the connectivity between vertices.
3. Iterate through the edges from the smallest cost. If the two vertices connected by the edge are not yet connected, select this edge for the spanning tree and merge (union) them using the Union-Find.
4. When the number of selected edges reaches \(N-1\), all vertices are connected, and the minimum spanning tree is complete.
5. Using the total cost of the selected edges total_cost and the cost of the last selected edge (which is the maximum cost among the selected ones) max_cost, calculate and output total_cost + K * max_cost.

Complexity

• Time Complexity: \(O(M \log M)\)

  • Sorting the edges takes \(O(M \log M)\).
  • Each operation on the Union-Find (same, merge) can be performed in almost constant time \(O(\alpha(N))\) using the inverse Ackermann function \(\alpha(N)\), so the processing of the entire loop is \(O(M \alpha(N))\).
  • As a whole, sorting is the bottleneck, resulting in a time complexity of \(O(M \log M)\). This runs sufficiently fast for the constraint \(M \le 2 \times 10^5\).

• Space Complexity: \(O(N + M)\)

  • We use \(O(M)\) memory for the array storing the edge information, and \(O(N)\) memory for managing the Union-Find.

Key Implementation Details

• Conversion from 1-indexed to 0-indexed The input vertex numbers are from \(1\) to \(N\), but to make them easier to handle internally and in the Union-Find, we subtract 1 to convert them to \(0\) through \(N-1\) when receiving the input.

• Countermeasure against overflow The total cost and the load index can be very large (up to approximately \(2 \times 10^5 \times 10^6 + 10^6 \times 10^6 \approx 10^{12}\)). In C++, we use the long long type for these calculations and variables to prevent overflow.

• Utilization of AtCoder Library (ACL) Using atcoder/dsu allows us to implement Union-Find concisely and without bugs.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

struct Edge {
    int u, v;
    long long c;
    bool operator<(const Edge& other) const {
        return c < other.c;
    }
};

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
        edges[i].u--; // 0-indexed に変換
        edges[i].v--;
    }

    // 辺をコストの昇順にソート
    sort(edges.begin(), edges.end());

    dsu d(N);
    long long total_cost = 0;
    long long max_cost = 0;
    int edges_count = 0;

    for (const auto& edge : edges) {
        if (!d.same(edge.u, edge.v)) {
            d.merge(edge.u, edge.v);
            total_cost += edge.c;
            max_cost = max(max_cost, edge.c);
            edges_count++;
            if (edges_count == N - 1) {
                break;
            }
        }
    }

    long long ans = total_cost + K * max_cost;
    cout << ans << "\n";

    return 0;
}

This editorial was generated by gemini-3.5-flash-high.