赛道修建
【问题描述】
C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建m 条赛道。
C 城一共有 n 个路口,这些路口编号为 1,2, … , n,有 n − 1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为 ai和 bi,该道路的长度为 li。借助这 n − 1 条道路,从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e1, e2, … , ek,满足可以从某个路口出发,依次经过道路 e1, e2, … , ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。
【输入格式】
输入文件名为 track.in。
输入文件第一行包含两个由空格分隔的正整数 n, m,分别表示路口数及需要修建的赛道数。
接下来 n − 1 行,第 i 行包含三个正整数 ai, bi, li,表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
【输出格式】
输出文件名为 track.out。
输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。
【输入输出样例 1】

【输入输出样例 1 说明】
所有路口及适合于修建赛道的道路如下图所示:

道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。
需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9 + 10 + 5 + 7 = 31,为所有方案中的最大值。
【输入输出样例 2】

【输入输出样例 2 说明】
所有路口及适合于修建赛道的道路如下图所示:

需要修建 3 条赛道。可以修建如下 3 条赛道:
1. 经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6 + 9 = 15;
2. 经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4 + 3 + 5 + 4 = 16;
3. 经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7 + 10 = 17。
长度最小的赛道长度为 15,为所有方案中的最大值。
【数据规模与约定】
所有测试数据的范围和特点如下表所示

其中,“分支不超过 3”的含义为:每个路口至多有 3 条道路与其相连。对于所有的数据,2 ≤ n≤ 50,000,1 ≤ m ≤ n − 1,1 ≤ ai, bi ≤ n,1 ≤ li ≤ 10,000。
查看答案与解析
答案:<p style="text-align: left;">#include <iostream></p><p style="text-align: left;">#include <algorithm></p><p style="text-align: left;">#include <cstdio></p><p style="text-align: left;">#include <cstring></p><p style="text-align: left;">#include <cmath></p><p style="text-align: left;">#include <set></p><p style="text-align: left;">#include <vector></p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int head[50100],to[100100],nex[100100],val[100100];</p><p style="text-align: left;">int n,waysnumber,m,edges;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">multiset <int> :: iterator it;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int dfs(int now,int father,int x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>multiset <int> son;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int v = head[now]; v ; v = nex[v])</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (to[v] != father){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int tmpways = dfs(to[v],now,x) + val[v];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (tmpways >= x) ++waysnumber;</p><p style="text-align: left;"><span style="white-space:pre"> </span>else son.insert(tmpways);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>//对当前点now的所有子路径进行组合,用刚好能满足≥x的最小的边组合</p><p style="text-align: left;"><span style="white-space:pre"> </span>//并返回所有儿子中最长的无法被组合成满足条件路的点 </p><p style="text-align: left;"><span style="white-space:pre"> </span>int maxwaylen = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (son.size() > 1){</p><p style="text-align: left;"><span style="white-space:pre"> </span>it = son.lower_bound(x - *son.begin());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (it == son.begin()) it++; //若最短的边≥x的时候,则用最短的两条边组合 </p><p style="text-align: left;"><span style="white-space:pre"> </span>if (it == son.end()){ //当前最短的边没办法找到够长的边组合出满足条件的路 </p><p style="text-align: left;"><span style="white-space:pre"> </span>//挑一条最长的子边返回 </p><p style="text-align: left;"><span style="white-space:pre"> </span>maxwaylen = max(maxwaylen,*son.begin());</p><p style="text-align: left;"><span style="white-space:pre"> </span>son.erase(son.begin());</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else{</p><p style="text-align: left;"><span style="white-space:pre"> </span>//成功组合出了满足条件的边 </p><p style="text-align: left;"><span style="white-space:pre"> </span>++waysnumber;</p><p style="text-align: left;"><span style="white-space:pre"> </span>son.erase(it);</p><p style="text-align: left;"><span style="white-space:pre"> </span>son.erase(son.begin());</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (son.size() == 1) maxwaylen = max(maxwaylen,*son.begin());</p><p style="text-align: left;"><span style="white-space:pre"> </span>return maxwaylen;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">bool check(int x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>waysnumber = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(1,0,x);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (waysnumber >= m) return true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>else return false;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void addedge(int u,int v,int c){</p><p style="text-align: left;"> nex[++edges] = head[u], head[u] = edges, to[edges] = v, val[edges] = c;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>edges = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d%d",&n,&m);</p><p style="text-align: left;"><span style="white-space:pre"> </span>long long all = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int i = 1 ; i < n ; ++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a,b,c;scanf("%d%d%d",&a,&b,&c);</p><p style="text-align: left;"><span style="white-space:pre"> </span>addedge(a,b,c);</p><p style="text-align: left;"><span style="white-space:pre"> </span>addedge(b,a,c);</p><p style="text-align: left;"><span style="white-space:pre"> </span>all += c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int l = 0 , r = all / m,mid,ans; //这里存在一个坑,对于ai = 1的图,如果这里的 r 使用极大值500000000,就会超时</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (l <= r){</p><p style="text-align: left;"><span style="white-space:pre"> </span>mid = (l + r) >> 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (check(mid)) ans = mid,l = mid + 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>else r = mid - 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%d\n",ans);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">} </p>
这道题暂未补解析。