这是一个典型的 图论 + 二分答案 (Binary Search) 问题。我们需要结合 最小生成树 (MST) 的思想和 贪心策略 来解决。

核心思路

  1. 二分答案 (Binary Search):

    • 题目要求找到最小的 。
    • 如果我们设定一个阈值 ，国家修好了所有 的路。如果在这个 下牛牛能修通道路且预算充足，那么对于任何比 大的阈值，牛牛花费只会更少（因为国家修的路更多了）。
    • 这种单调性决定了我们可以对 进行二分搜索。二分范围是 （即 的最大值）。

  2. 最小生成树策略 (Kruskal's Algorithm):

    • 对于一个固定的 ，所有 的边权视为 （免费）。所有 的边权视为 （牛牛需要付费）。
    • 为了让图连通且花费最小，我们需要构建一棵生成树。根据 Kruskal 算法，我们应该优先选择权值小的边。
    • 由于免费边的权值（实际上是 ）一定小于付费边的权值（），所以我们总是先连接所有能用的免费边。如果图还没连通，再从付费边中从小到大选择，直到图连通。

  3. 费用计算的贪心策略:

    • 题目中提到：“第 次修复操作花费 ”。
    • 假设牛牛选定了一组需要修复的边 。为了让总花费 最小，我们需要决定修复的顺序。
    • 根据排序不等式（或者直观贪心）：我们要让大的权重乘上小的系数 ，小的权重乘上大的系数 。
    • 结论： 牛牛应该先修最贵的路（），最后修最便宜的路。所以在计算成本时，我们将选出的付费边从大到小排序，依次乘以 来计算总花费。

算法步骤

  1. 将所有边按损坏值 从小到大排序。
  2. 二分搜索 的值（范围 ）。
  3. check(p) 函数逻辑：
    • 使用并查集 (DSU) 维护连通性。
    • 遍历排序后的边：
      • 如果边权 ，且连接了两个不同的连通块，直接合并（免费）。
      • 如果边权 ，且连接了两个不同的连通块，记录该边权到列表 paid_edges 中，并合并。
    • 检查是否所有城市都连通（连通块数量为 1）。
    • 将 paid_edges 从大到小排序。
    • 计算总花费 。
    • 如果总花费 ，则该 可行。

C++ 代码实现

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

struct Edge {
    int u;
    int v;
    ll w;
};

bool compareEdge(const Edge& a, const Edge& b) {
    return a.w < b.w;
};

class DSU {
  private:
    vector<int> parent;
    int components;

  public:
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            components--;
            return true;
        }
        return false;
    }

    bool connected() {
        return components == 1;
    }
};

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

    int n, m;
    ll c;
    cin >> n >> m >> c;

    vector<Edge> roads(m);
    for (int i = 0; i < m; i++)
        cin >> roads[i].u >> roads[i].v >> roads[i].w;

    sort(roads.begin(), roads.end(), compareEdge);

    auto check = [&](int p) -> bool {
        DSU dsu(n);
        vector<int> roadCost;

        for (const Edge& road : roads) {
            if (dsu.connected())
                break;
            if (dsu.find(road.u) != dsu.find(road.v)) {
                if (road.w  > p) {
                    roadCost.push_back(road.w);
                }
                dsu.unite(road.u, road.v);
            }
        }

        if (!dsu.connected())
            return false;

        sort(roadCost.begin(), roadCost.end(), greater<>{});

        ll totalCost = 0;
        for (int i = 0; i < roadCost.size(); i++)
            totalCost += (ll)(i + 1) * roadCost[i];
        if (totalCost > c)
            return false;

        return totalCost <= c;
    };

    ll low = 0;
    ll high = 1e9 + 1;

    while (low < high) {
        ll mid = low + (high - low) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << high << endl;
}

复杂度分析

  1. 排序: 主函数中对所有边排序一次，时间复杂度 。
  2. 二分搜索: 二分范围 ，大约循环 次。
  3. Check 函数:
    • 遍历所有边并进行并查集操作，近似 （因并查集带路径压缩和按秩合并，接近常数）。
    • 对选出的 paid_edges 排序。最坏情况下选出的边数接近 ，排序 。
    • 单次 check 复杂度约为 。
  4. 总复杂度: 。对于 ，这完全可以在 1 秒内运行完成。