首页 > 试题广场 >

旅游

[编程题]旅游

热度指数：6 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 有 $n$ 个城市， $m$ 条连接两个城市的双向道路，每条道路有个损坏值 $a_i$ ，牛牛手里有 $c$ 元，进行第 $k$ 次修复道路操作时需要 $k\times a_i$ 元。
$\hspace{15pt}$ 国家愿意修复损坏值 $\le p$ 的道路，牛牛不需要再花钱修国家帮忙修的路。
$\hspace{15pt}$ 牛牛可以自行决定修复哪些道路以及修复它们的顺序。问 $p$ 至少为多少，牛牛才能用不超过 $c$ 元的总花费使得任意两座城市间可以通过修好的道路互相到达。如果国家不需要修复任何道路，输出 $0$ 。

输入描述:

第一行三个正整数 。
此后  行，第  行输入三个正整数 ，表示第  条边连接城市  和城市 ，损坏值为 。保证无自环，图连通；但是可能存在重边。

输出描述:

在一行上输出一个整数，表示完成目标所需  的最小值。

示例1

输入

输出

说明

当  时，国家免费修复了连接城市  和  的道路。为使所有城市连通，牛牛可以进行如下操作：
修复连接  的道路，花费  元；
修复连接  的道路，花费  元。
共花费  元，能达成目标。

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-19 优化题面文本与格式；修正样例解释笔误。

算法知识视频讲解

Yui___

最小生成树问题

使用的算法是：Kruskal算法

#include <algorithm>
#include <iostream>
#include <vector>


//并查集
class DisjointSet
{
public:
    DisjointSet(int n)
    {
        size = n+1;
        fa.resize(size);
        rank.resize(size);
        init();
    }

    int find(int x)
    {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }

    bool meger(int a,int b)
    {
        int x = find(a),y = find(b);
        if(x == y)
        {
            return true;
        }

        if(rank[x] > rank[y])
        {
            //简单合并到复杂
            fa[y] = x;
        }
        else
        {
            if(rank[x] == rank[y])
            {
                rank[y]+=1;
            }
            fa[x] = y;
        }
        return false;
    }

private:
    void init()
    {
        for(int i = 1;i < size;++i)
        {
            fa[i] = i;
            rank[i] = 1;
        }
    }

private:
    std::vector<int> fa; // 存储当前节点的父节点
    std::vector<int> rank; //存储当前节点的秩
    int size;
};


struct Path
{
    int x;
    int y;
    long long a;
};

int main()
{
    int n = 0,m = 0;
    long long c = 0;
    std::cin>>n>>m>>c;

    std::vector<Path> paths(m);
    for(int i = 0;i < m;++i)
    {
        auto& it = paths[i];
        std::cin>>it.x>>it.y>>it.a;
    }

    DisjointSet disjointSet(n);

    std::sort(paths.begin(),paths.end(),[](Path a,Path b){
        return a.a < b.a;
    });

    //最小生成树
    std::vector<long long> moneys;
    for(int i = 0;i < m;++i)
    {
        Path& tmp = paths[i];
        if(!disjointSet.meger(tmp.x,tmp.y))
        {
            moneys.push_back(tmp.a);
        }
    }
    std::sort(moneys.begin(),moneys.end(),std::greater<long long>());
    long long ans = 0,cur_num = 1;

    for(long long&it : moneys)
    {
        if(c - cur_num*it < 0)
        {
            ans = it;
            break;
        }
        c -= cur_num*it;
        cur_num+=1;
    }

    std::cout<<ans<<'\n';

}

发表于 2025-11-19 10:25:26 回复(0)

提交观点

问题信息

难度：

1条回答 6收藏 8浏览

旅游

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

相关试题