Overview

This problem asks us to find a set of cables that connects all sites and minimizes the “total cost \(+ K \times\) maximum cost”. This can be solved by finding the Minimum Spanning Tree (MST).

Analysis

A Tree is Sufficient for Connectivity

To connect all sites, it is sufficient for the set of edges \(S\) to form a spanning tree (a tree with \(N-1\) edges connecting all vertices). Even if we add extra edges that create cycles, the total cost \(\sum c_i\) will only increase, and the maximum cost \(\max c_i\) will not decrease. Therefore, the set \(S\) that minimizes the load index must be a tree. Thus, we can narrow down our candidates to “spanning trees”.

Can We Minimize Both Terms of the Load Index Simultaneously?

The load index consists of the following two terms:

\[ \left(\sum_{i \in S} c_i\right) + K \times \max_{i \in S} c_i \]

At first glance, “minimizing the total cost” and “minimizing the maximum cost” seem like separate optimization problems, suggesting a trade-off. However, there is an important fact here:

• The Minimum Spanning Tree (MST) minimizes the total cost \(\sum c_i\).
• The MST is also a “minimum bottleneck spanning tree” (a spanning tree that minimizes the maximum edge cost).

The second property is crucial. In fact, the maximum cost of an edge in an MST is equal to the minimum possible maximum cost among all spanning trees (this is the property of the minimum bottleneck spanning tree).

In other words, the MST simultaneously minimizes both \(\sum c_i\) and \(\max c_i\). Therefore, the load index, which is the sum of these two terms, is also minimized by the MST. There is no need to worry about a trade-off.

Issues with a Naive Approach

A naive approach of enumerating all spanning trees and comparing their load indices is impossible because the number of spanning trees grows exponentially. Based on the analysis above, we know that we only need to find a single MST.

Algorithm

We construct the Minimum Spanning Tree using Kruskal’s algorithm.

1. Sort all edges in ascending order of their cost \(c_i\).
2. Process the edges in ascending order of cost. Using a Union-Find (DSU) data structure, repeat the process: “If the endpoints of the edge are not yet connected, add the edge to the spanning tree.”
3. Once the number of chosen edges reaches \(N-1\), the spanning tree is complete.

During this process, we record: - \(\text{sum}\) = the sum of the costs of the chosen edges - \(\text{maxc}\) = the maximum cost among the chosen edges

Since we process the edges in ascending order of cost, the cost of the last chosen edge will be the maximum cost.

The final answer is:

\[ \text{ans} = \text{sum} + K \times \text{maxc} \]

Example

For example, with 3 vertices, edges \((1,2,c=2),\ (2,3,c=3),\ (1,3,c=5)\), and \(K=2\): - The MST chooses the edges with costs \(2\) and \(3\), giving \(\text{sum}=5\) and \(\text{maxc}=3\). - Load index \(= 5 + 2 \times 3 = 11\).

We can confirm that this is smaller than any spanning tree that uses the edge with cost \(5\).

Complexity

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

Implementation Details

• If we store the edges in an array as {c, u, v}, sorting them will naturally order them by cost in ascending order.

• Since we process edges in ascending order, we can simply overwrite maxc with the cost of the last chosen edge to get the maximum value (there is no need to even take the max each time).

• Since \(c_i \le 10^6\), \(N \le 2\times10^5\), and \(K \le 10^6\), the sum and \(K \times \text{maxc}\) can exceed 32-bit integer limits. Thus, we should use long long (64-bit integer) for calculations.

• Union-Find should be optimized using path compression and union by rank (or size) for efficiency.

  Source Code

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
    int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
};

int main(){
    int N, M; long long K;
    scanf("%d %d %lld", &N, &M, &K);
    vector<array<long long,3>> edges(M); // c, u, v
    for(int i=0;i<M;i++){
        long long u,v,c;
        scanf("%lld %lld %lld", &u, &v, &c);
        edges[i] = {c, u-1, v-1};
    }
    sort(edges.begin(), edges.end());
    DSU dsu(N);
    long long sum = 0, maxc = 0;
    int cnt = 0;
    for(int i=0;i<M && cnt<N-1;i++){
        long long c = edges[i][0];
        int u = (int)edges[i][1], v = (int)edges[i][2];
        if(dsu.unite(u,v)){
            sum += c;
            maxc = c; // 昇順なので最後が最大
            cnt++;
        }
    }
    long long ans = sum + K * maxc;
    printf("%lld\n", ans);
    return 0;
}

---

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