题意 你有一颗 个节点的有根树 (以 号节点为根) ，求最少加入多少条边之后使得根节点（即 11 号节点）到这棵树上任意一点的距离不大于 。 分析 我们考虑覆盖一个节点有多少种方法。 在父亲节点连一条边。 在儿子节点上连一条边。 在当前节点上连一条边。 这样我们发现并不是很好做，考虑叶子
展开全文
题意 你有一颗 个节点的有根树(以 号节点为根)，求最少加入多少条边之后使得根节点（即 号节点）到这棵树上任意一点的距离不大于 。 分析 考虑一种贪心，如果一个节点 到根的距离大于 的话，那么我们就从根节点连一条边到 节点的父亲 。 来考虑正确性的证明，一个节点 到根的距离如果大于了
展开全文
题目描述 Solution #include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__)
展开全文
Tree with Small Distances 分析 居然还要看按照深度进行操作，大意了，没有学 其实就是一个贪心。因为如果这个点距离根节点超过2，只需要考虑边加在哪里。有三个选择：父节点，自己，子节点。选择父节点更优。记录两个数组： vis[i]:此节点是否与根节点直接相连
op[i]:此
展开全文
分析 首先我们知道如若当前点需要连边，那么一定是直接连1号点最优接下来，我们考虑贪心，从底部向上进行一个点需要被连边当且仅当它的儿子中有一个没有被覆盖到（因为当前点和1连边之后只能多辐射一个距离内的点）我们记录状态 0表示没有被子孙中的点覆盖 1表示被儿子覆盖 2表示没有被覆盖，需要父亲的人覆盖
展开全文
题意： 个点条边的无向连通图，问最少加多少条边才能使顶点到任意一个点不超过两条边。 思路：一种贪心的策略是如果某个点到根结点的边数超过二就把该节点的父结点和根结点连条边 检验刚开始的策略： 连了这条边后，的边数都变成了因为没有考虑到结点和根结点连边对父结点的影响，导致多连了一条边 正确的方案
展开全文
题意：给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？ 思路：你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。 代码： #include<bits/s
展开全文
思路 1.先对树从根结点进行一遍dfs求出每个点的深度 2.用大根堆把不满足要求的点存起来 3.按深度从大到小依次把该点的父亲结点与根结点相连 4.更新父亲结点和它的子节点的状态 代码 // Problem: Tree with Small Distances
// Contest: NowCo
展开全文
传送门 观察发现一定是从连出来的边最划算 而且连到一个点之后,这个点周围的所有点都是满足要求的. 定义为和有连边 为通过父亲到 为通过儿子到 那么 那么 但是如果的儿子没有一个和有边,还需要选一个儿子和相连... #include <bits/stdc++.h>
using names
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
