这是一个典型的 图论 + 二分答案 (Binary Search) 问题。我们需要结合 最小生成树 (MST) 的思想和 贪心策略 来解决。
核心思路
二分答案 (Binary Search):
题目要求找到最小的 。
如果我们设定一个阈值 ，国家修好了所有 的路。如果在这个 下牛牛能修通
展开全文
本题是一道最小生成树的kruskal算法的题目
先用kruskal算法去记录最小生成树的最短边
然后根据题意所给出的要求去进行迭代更新sum，直至找到一个sum值大于牛牛所投入的资金c，输出最后令
sum>=c的损害值
#include<iostream>
#include<
展开全文
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
展开全文
#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(
展开全文
我们不难发现答案是单调的（政府给得越多，我们越能多修路），贪心来说，我们需要修花费少的n-1条路，那么我们可以使用最小生成树找出需要修的边，再利用二分来查找政府的最小帮助的钱是多少。二分的时候不难发现，我们需要把修路花费钱多的路放在一开始来修，因为如果放在后面修，会累计出来，多增加k倍数的钱。
#i
展开全文
显然只需要 MST 上的那 条边，先求一遍 MST 过程中把边拿出来。
然后找 的时候也不用二分，因为 取值一定是那些边的边权，遍历并判断就行了。
关于答案的计算，一开始只会修 次，因为就那些边，随便算算就行了。
Code:
#include<bits/stdc++.h>
us
展开全文
本道题算是最小生成树的变种吧，写的不是非常熟练，特别是并查集，太少写了，所以犯下了很多低级错误
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
class unit
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
