Overview

This problem asks us to find a spanning tree of a given undirected graph that minimizes the “load index”, which is the sum of the “total cost of the edges” and “the maximum edge cost \(\times K\)”.

Analysis

The load index is the sum of the chosen edges \(\sum c_i\) plus \(K\) times the maximum cost \(\max c_i\). Here, let us consider fixing the maximum cost of the adopted edges to \(X\). Having a maximum cost of \(X\) means that the available edges are restricted to those with a cost of \(X\) or less. If we try to construct a spanning tree under this constraint, we can see that to minimize the total cost, we should construct a minimum spanning tree (MST) using only edges with a cost of \(X\) or less.

To find the candidate values of the maximum cost \(X\) that can connect all vertices, we consider trying all edge costs \(c_i\) given in the input. We sort the edges in ascending order of their costs and add them one by one in that order, similar to Kruskal’s algorithm. By doing this, the “sum of the used edges” at the point where edges up to a certain cost \(X\) have been added is precisely the “cost of the minimum spanning tree constructed using only edges with a cost of \(X\) or less”.

The load index \(\text{mst\_sum} + K \times X\) is minimized at the moment the entire graph becomes connected for the first time with the maximum cost \(X\). This is because for any larger maximum cost \(X'\) obtained by adding edges with higher costs, the total sum of edge costs either remains the same or increases, and the penalty term \(K \times X'\) also increases, meaning the solution can never improve.

Algorithm

1. Sort the edges in ascending order of their costs.
2. Initialize a Union-Find tree and set the total edge cost mst_sum = 0.
3. Process edges with the same cost together. For each group of edges with the same cost, if there is an edge connecting vertices that are not yet connected, unite them using Union-Find and add its cost to mst_sum.
4. After processing all edges of that cost, check if the entire graph has become connected (i.e., all vertices belong to the same group).
5. If it is connected, the value of “mst_sum + K \(\times\) current edge cost” at that moment is the minimum load index. Output this value and terminate.

Complexity

• Time Complexity: \(O(M \log M + M \alpha(N))\). Sorting takes \(O(M \log M)\), and Union-Find operations take \(O(M \alpha(N))\).
• Space Complexity: \(O(N + M)\). This is required to store the graph information and the Union-Find tree.

Implementation Points

It is important to process edges with the same cost together. If you were to add edges of the same cost one by one and check connectivity in between, you would end up checking connectivity multiple times for the same maximum cost, which complicates the logic. Checking connectivity only after all edges of a specific cost have been added allows for a clean and simple implementation. Also, since \(N\) and \(M\) can be large, pay attention to fast I/O (such as ios_base::sync_with_stdio(false)) and ensure that the answer fits within a 64-bit integer (using the long long type).

Source Code

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

using namespace std;
using namespace atcoder;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    long long K;
    cin >> N >> M >> K;
    
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
        edges[i].u--;
        edges[i].v--;
    }
    
    sort(edges.begin(), edges.end());
    
    dsu d(N);
    long long mst_sum = 0;
    long long ans = 4e18;
    
    for (int i = 0; i < M; ) {
        int j = i;
        while (j < M && edges[j].c == edges[i].c) {
            if (!d.same(edges[j].u, edges[j].v)) {
                d.merge(edges[j].u, edges[j].v);
                mst_sum += edges[j].c;
            }
            j++;
        }
        if (d.size(0) == N) {
            ans = min(ans, mst_sum + K * edges[i].c);
            break;
        }
        i = j;
    }
    
    cout << ans << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.