Overview

For a set of cables \(S\) that connects all bases, we want to minimize

\[ \sum_{i \in S} c_i + K \times \max_{i \in S} c_i \]

This is a problem of minimizing the above expression. In conclusion, we just need to find a standard Minimum Spanning Tree (MST).

Analysis

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

Now, consider the case where \(S\) contains a cycle.
Even if we remove one edge from the cycle, the graph remains connected.

Furthermore, since all edge costs are positive, removing an edge always decreases the total cost.
Additionally, the maximum edge cost will not increase.

Therefore, the optimal solution must be a spanning tree with \(N-1\) edges.

---

Next, the objective function is not just the total cost, but:

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

At first glance, it might seem necessary to look for a special tree that takes the maximum edge cost into account, rather than just the minimum spanning tree.

However, the Minimum Spanning Tree (MST) has the following important properties:

• An MST has the minimum total cost.
• An MST also minimizes the maximum edge cost.

The latter is the property of the “Minimum Bottleneck Spanning Tree”.

In other words, for any spanning tree \(T\), if we denote the MST as \(T_{\text{mst}}\), then:

\[ \sum_{e \in T_{\text{mst}}} c_e \leq \sum_{e \in T} c_e \]

and

\[ \max_{e \in T_{\text{mst}}} c_e \leq \max_{e \in T} c_e \]

hold true.

Since \(K\) is a non-negative integer in this problem,

\[ K \times \max_{e \in T_{\text{mst}}} c_e \leq K \times \max_{e \in T} c_e \]

also holds true.

Therefore,

\[ \sum_{e \in T_{\text{mst}}} c_e + K \times \max_{e \in T_{\text{mst}}} c_e \leq \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \]

which shows that the MST is optimal.

---

If we naively try all cable sets, there are \(2^M\) candidates, which is far too slow since \(M \leq 2 \times 10^5\).

Also, an approach such as fixing the maximum edge cost and constructing a spanning tree each time can be very heavy depending on the implementation.

For this problem, it is sufficient to find the MST just once.

Algorithm

We find the minimum spanning tree using Kruskal’s algorithm.

The steps are as follows:

1. Sort all edges in ascending order of their cost \(c_i\).
2. Prepare a Union-Find (DSU) data structure.
3. Iterate through the edges in ascending order of cost.
4. If adding the edge does not create a cycle, include it in the MST.
5. For each included edge:
   • Add \(c_i\) to the total cost sum.
   • Update the maximum edge cost mx.
6. Terminate once the number of included edges reaches \(N-1\).
7. The answer is

\[ \text{sum} + K \times \text{mx} \]

Since Kruskal’s algorithm includes edges in ascending order of their costs, we obtain a spanning tree with the minimum total cost.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the edges is the bottleneck.
  • Union-Find operations take almost constant time.
• Space Complexity: \(O(N + M)\)
  • We store the array of edges and the Union-Find structures.

Implementation Points

• Use a 64-bit integer type (such as long long in C++) because the answer can be large.

  • For example, \(K \times \max c_i\) can be up to \(10^6 \times 10^6 = 10^{12}\).

• In the Union-Find, using path compression and union by size (or rank) makes it fast.

• Since the vertex indices in the input are 1-based, we convert them to 0-based in the implementation.

• Once the number of included edges reaches \(N-1\), there is no need to examine any more edges.

  Source Code

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

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

struct Edge {
    int u, v, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<Edge> edges(M);
    for (auto &e : edges) {
        cin >> e.u >> e.v >> e.c;
        --e.u;
        --e.v;
    }

    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.c < b.c;
    });

    DSU dsu(N);
    long long sum = 0;
    long long mx = 0;
    int cnt = 0;

    for (const auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            sum += e.c;
            mx = max(mx, (long long)e.c);
            cnt++;
            if (cnt == N - 1) break;
        }
    }

    cout << sum + K * mx << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.