A.最小生成树可以用最小生成树写，不过稍微想一下就可以想到，从小到大排序后a[1]和其他个点连接就是最小生成树。C.Shopping可以半价的物品的个数为，排序之后max个物品半价，其余原价即是答案。B.病毒感染B.病毒感染 题意：给出一颗所有路径都为1的树，让你找出到其余点距离和最小的点，若存在多
展开全文
链接：https://ac.nowcoder.com/acm/contest/6173/A 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1048576K，其他语言2097152K64bit IO Format: %lld 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非
展开全文
链接：https://ac.nowcoder.com/acm/contest/6173/D 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld 题目描述 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域
展开全文
链接：https://ac.nowcoder.com/acm/contest/6173/C 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld 题目描述 你要买n件物品，其中有一些是凳子。商场正在举行促销活
展开全文
最小生成树 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av 现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他 可以用prim算法跑出来最小生成树，但是仔细想可以用
展开全文
链接
解题思路如下：
由于输入给的是各点的点权而不是边权，要得要最小生成树（题目要求的输出是边权）
找出点权最小的点A，让其与（n-1）各点相连，在这里A的点权被运用了（n-1）次，而其余各点的点权被使用一次。就拿题目输入的来说，最后得到的输出是（1+2）+（1+3）得到的，实际上就是1*（3-1
展开全文
题目 有一张 个点的带权无向图，这张无向图是一张完全图。第 个点有一个点权 ，边 的权值为 。找一个这张图的边权之和最小的生成树。 解题思路 生成树有 n-1 条边，每个的点权至少要加一次。选取点权最小的那个点作为根节点，将其他的点都作为该节点的子节点，即是边权之和的最小生成树。注意：当只有
展开全文
找出权值最小的点，让其余的点与该点相连 #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=500000;
int head[maxn],f[maxn],a[maxn],cnt
展开全文
题意：有n个点的完全无向图，每个点i有一个点权a[i],每两个点之间之间的边权大小为这两个点的点权和贪心方法：找到一个最小的点，要使得最后的结果最小，只需要把这个点和其他所有点连接的边权和求出即可代码： #include <iostream>
#include<cmath>
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
