首页 > 最小生成树
开通博客写题解
头像 chen颜
发表于 2020-07-01 15:52:34
A.最小生成树可以用最小生成树写，不过稍微想一下就可以想到，从小到大排序后a[1]和其他个点连接就是最小生成树。C.Shopping可以半价的物品的个数为，排序之后max个物品半价，其余原价即是答案。B.病毒感染B.病毒感染 题意：给出一颗所有路径都为1的树，让你找出到其余点距离和最小的点，若存在多 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 tin_t
发表于 2020-07-04 18:47:53
链接：https://ac.nowcoder.com/acm/contest/6173/A 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1048576K，其他语言2097152K64bit IO Format: %lld 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 tin_t
发表于 2020-07-04 18:59:10
链接：https://ac.nowcoder.com/acm/contest/6173/D 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld 题目描述 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 tin_t
发表于 2020-07-04 19:20:03
链接：https://ac.nowcoder.com/acm/contest/6173/C 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld 题目描述 你要买n件物品，其中有一些是凳子。商场正在举行促销活 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 acwing_云算法
发表于 2020-07-11 13:30:13
最小生成树 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av 现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他 可以用prim算法跑出来最小生成树，但是仔细想可以用 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 东溪看水
发表于 2020-07-03 10:36:37
题目 有一张 个点的带权无向图，这张无向图是一张完全图。第 个点有一个点权 ，边 的权值为 。找一个这张图的边权之和最小的生成树。 解题思路 生成树有 n-1 条边，每个的点权至少要加一次。选取点权最小的那个点作为根节点，将其他的点都作为该节点的子节点，即是边权之和的最小生成树。注意：当只有 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 cheeserish
发表于 2020-07-01 08:43:20
找出权值最小的点，让其余的点与该点相连 #include<bits/stdc++.h> using namespace std; #define int long long const int maxn=500000; int head[maxn],f[maxn],a[maxn],cnt 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 y_din
发表于 2020-07-01 11:31:08
题意：有n个点的完全无向图，每个点i有一个点权a[i],每两个点之间之间的边权大小为这两个点的点权和贪心方法：找到一个最小的点，要使得最后的结果最小，只需要把这个点和其他所有点连接的边权和求出即可代码： #include <iostream> #include<cmath> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 y_din
发表于 2020-07-01 11:34:01
题意：n件物品，里面有一些凳子，有m个购物车，每个物品有一个权值a[i]和b[i],分别表示价值大小和是否为凳子，若一个购物车里有凳子，则这个购物车里的价格最高的物品半价贪心方法：我们可以发现有凳子除了影响半价没有其他影响了，所以我们只需要考虑一下有几个可以半价就可以了，于是我们就可以只计算一下购物 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 y_din
发表于 2020-07-01 11:35:18
题意：有n张地毯，后铺的在最上面，给你一个点，问这个点最上面的地毯的编号是什么贪心方法：因为在最上面的地毯肯定在后面，所以我们只需要倒着找就可以了代码： #include<cstdio> #include<iostream> #include<algorithm> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”