题目描述
C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 mm 条赛道。
C 城一共有 nn 个路口,这些路口编号为 1,2,…,n1,2,…,n,有 n-1n−1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 ii 条道路连接的两个路口编号为 a_iai 和 b_ibi,该道路的长度为 l_ili。借助这 n-1n−1 条道路,从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e_1,e_2,…,e_ke1,e2,…,ek,满足可以从某个路口出发,依次经过 道路 e_1,e_2,…,e_ke1,e2,…,ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的 mm 条赛道中长度最小的赛道长度最大(即 mm 条赛道中最短赛道的长度尽可能大)
输入输出格式
输入格式:
输入文件第一行包含两个由空格分隔的正整数 n,mn,m,分别表示路口数及需要修建的 赛道数。
接下来 n-1n−1 行,第 ii 行包含三个正整数 a_i,b_i,l_iai,bi,li,表示第 ii 条适合于修建赛道的道 路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n-1n−1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
输出格式:
输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。
题意 一棵树 给定建m条赛道 要使得这m条赛道中最短的赛道最长 赛道上每一条边只经过一次
解题方法
m = 1 贪心求树的直径就完事了
链上部分分 二分 最短的赛道的长度 上界为直径 下界为1 nlog所有边边长和 完事了
菊花图 将权值排序 将最大的与第m大的组成赛道 第二大与第m-1大组成赛道 .... 完事了
55pts get
满分做法
我们要做的是在使最多的儿子对答案做出贡献的同时,传递上去的值是最大的
具体做法如下
二分最短赛道的长度
1.每个树节点 保存子节点传来的最大值加上与该节点的连边长度。若该值大于等于k 则答案+1。 若小于k 将该值插入multiset集合 (将该值往上传)。
2.然后处理multiset集合中的元素 若集合仅有一个元素 那将该元素传至父节点(该数是传至父节点的最大的数)
若有多个元素 找到第一个大于等于k-begin的数 (即能和begin组成一条赛道的数)
如果该数等于begin且begin仅有一个数 (这种情况一般是begin>k-begin) 迭代器++
找下一个大于他的数 如果迭代器等于end 即找不到与begin组成大于k的数 将begin删除 如果找到 begin和该数一同删除 答案++ 然后就解决啦!
#include <cstdio> #include <algorithm> #include <set> #include <iostream> using namespace std; const int M = 100005; int head[M],nxt[M],to[M],c[M]; int val; int ans; int size; int n ,m; int zj,gd; multiset<int> s[M]; multiset<int> ::iterator it; void add(int u ,int v,int w) { nxt[++size] = head[u]; head[u] = size; to[size] = v; c[size] = w; } void dfs(int now,int fa,int k) // 求树的直径 { if(k > zj) gd = now,zj = k; for(int i = head[now];i;i = nxt[i]) { if(to[i] == fa) continue; dfs(to[i],now,k+c[i]); } } int dfs1(int now,int fa,int k) { s[now].clear(); for(int i = head[now];i;i = nxt[i]) { if(to[i] == fa) continue; val = dfs1(to[i],now, k) + c[i]; if(val >= k) ans++; else s[now].insert(val); } int Max = 0; while(!s[now].empty()) { if(s[now].size() == 1) return max(Max,*s[now].begin()); it = s[now].lower_bound(k-*s[now].begin()); if(it == s[now].begin()&&s[now].count(*it) == 1) it++; if(it == s[now].end()) { Max = max(Max,*s[now].begin()); s[now].erase(s[now].find(*s[now].begin())); } else{ ans++; s[now].erase(s[now].find(*s[now].begin())); s[now].erase(s[now].find(*it)); } } return Max; } bool check(int k) { ans = 0; dfs1(1,0,k); if(ans >= m) return true; else return false; } int main(){ scanf("%d%d",&n,&m); int u , v , w; for(int i = 1;i <= n - 1;i++) { scanf("%d%d%d",&u,&v,&w); add(u ,v , w); add(v , u ,w); } dfs(1,0,0); // dfs(gd,0,0); // 两遍dfs求树的直径 int l = 1,r = zj; while(l < r) { int mid = (l + r + 1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } printf("%d",l); }
- 还没有人评论,欢迎说说您的想法!