首页 > 试题广场 >

旅游

[编程题]旅游

热度指数：1474 时间限制：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 优化题面文本与格式；修正样例解释笔误。

算法知识视频讲解

此在Dasein

发表于 2025-11-19 05:07:17

这是一个典型的图论 + 二分答案 (Binary Search) 问题。我们需要结合最小生成树 (MST) 的思想和贪心策略来解决。核心思路二分答案 (Binary Search): 题目要求找到最小的。如果我们设定一个阈值，国家修好了所有的路。如果在这个下牛牛能修通展开全文

爱音乐的博博

发表于 2023-07-22 16:25:04

本题是一道最小生成树的kruskal算法的题目先用kruskal算法去记录最小生成树的最短边然后根据题意所给出的要求去进行迭代更新sum，直至找到一个sum值大于牛牛所投入的资金c，输出最后令 sum>=c的损害值 #include<iostream> #include< 展开全文

quchen666

发表于 2025-11-19 12:47:34

#include <bits/stdc++.h> typedef long long ll; const int N = 2e5+10; using namespace std; struct Node { int u,v; ll w; }e[N]; bool cmp( 展开全文

ddb酱

发表于 2025-11-19 10:06:13

#include <bits/stdc++.h> using namespace std; #define endl "\n" #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() 展开全文

Kato_Shoko

发表于 2025-11-19 14:15:45

我们不难发现答案是单调的（政府给得越多，我们越能多修路），贪心来说，我们需要修花费少的n-1条路，那么我们可以使用最小生成树找出需要修的边，再利用二分来查找政府的最小帮助的钱是多少。二分的时候不难发现，我们需要把修路花费钱多的路放在一开始来修，因为如果放在后面修，会累计出来，多增加k倍数的钱。 #i 展开全文