【NOIp 2018】赛道修建 / 题解

题目描述

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 $m$ 条赛道。

C 城一共有 $n$ 个路口,这些路口编号为 $1,2,…,n$,有 $n-1$ 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 $i$ 条道路连接的两个路口编号为 $a_i$ 和 $b_i$,该道路的长度为 $l_i$。借助这 $n-1$ 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 $e_1,e_2,…,e_k$,满足可以从某个路口出发,依次经过道路 $e_1,e_2,…,e_k$(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的 $m$ 条赛道中长度最小的赛道长度最大(即 $m$ 条赛道中最短赛道的长度尽可能大)

输入输出格式

输入格式

输入文件第一行包含两个由空格分隔的正整数 $n,m$,分别表示路口数及需要修建的赛道数。

接下来 $n-1$ 行,第 $i$ 行包含三个正整数 $a_i,b_i,l_i$,表示第 $i$ 条适合于修建赛道的道连接的两个路口编号及道路长度。保证任意两个路口均可通过这 $n-1$ 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

输出格式

输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。

样例

样例输入

9 3 
1 2 6 
2 3 3 
3 4 5 
4 5 10 
6 2 4 
7 2 9 
8 4 7 
9 4 4

样例输出

15

数据规模与约定

其中,“分支不超过 3” 的含义为:每个路口至多有 3 条道路与其相连。 对于所有的数据,$2 \leq n \leq 50,000$,$1 \leq m \leq n − 1$,$1 \leq a_i, b_i \leq n$,$1 \leq l_i \leq 10,000$。

思路

我就顺着我考场上的思路讲一讲这道题吧。

首先对于 $m=1$ 的数据,我们显然只要找到直径长度;

对于一条链的情况,二分答案,对于每次二分出来的 $mid$,从根开始贪心选取一段边,累计长度大于等于 $mid$ 的时候就计入答案,重新开始寻找下一段,得出对于 $mid$ 最大的答案,判断它是否大于 $m$;

对于菊花图,由于路径最多经过两条边,我们实质上是要在 $n-1$ 条边中选一共 $m$ 次,每次选出一条独立的边,或者一对边,使得最终每条边的长度 / 每对边的长度和尽量大。对于每次二分出来的 $mid$,长度大于 $mid$ 的边独立地选出,而小于 $mid$ 的边尝试一长一短两两配对,用双指针在排过序的长度数据中扫描一遍,得出对于 $mid$ 最大的答案,判断它是否大于 $m$;

对于 “分支不超过 3” 的图,也就是除根节点之外,每个点只有两个儿子,同样我们二分答案。首先定义几个概念,我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。暂时不考虑根节点,如果 $i$ 只有一个儿子 $v$,若 $f_v + l_i \geq mid$,直接将 $f_v + l_i$ 计入答案,否则,$f_i = f_v + l_i$;如果 $i$ 有两个儿子,如果它们可以直接单独计入答案则直接计入,否则考虑是否可以将这两个儿子牵引的两条半链合并,合并后长度大于 $mid$ 则直接计入答案,否则选取最长的一段转移到 $f_i$,对于可能有三个儿子的根节点,遵循的原则同样是尽量独立选取两个儿子,否则尝试合并两条半链计入答案;

如果我们结合菊花图和 “分支不超过 3” 的图这两种情况,我们就可以搞定 100% 的数据。继承上面半链和 $f_i$ 的定义,我们要做的是在使最多的儿子对答案做出贡献的同时,尽量大地将 $f_{son}$ 的值转移给 $f_i$。因为 $f$ 的一个值最多对答案产生 1 的贡献,所以使儿子做出更少贡献,转移更大的 $f_i$ 不可能使答案变优,我们的贪心第一关键字就可以设为使儿子做出最大的贡献。在菊花图的算法中,我们只满足了第一个条件,但不需要考虑 $f_i$ 进一步的转移,而我认为这一点正是 A 掉本题的重点。也就是说,我们要在儿子的 $f$ 值中,选出一个最优的转移至 $f_i$,使得剩下的 $f$ 值的合法匹配最多。同样可以二分转移至 $f_i$ 的儿子,剩下的和菊花图的做法相同。

总结一下正解:首先二分答案,贪心计算对于 $mid$ 的最大可能答案,判断它和 $m$ 的大小。我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。要求对于 $i$ 所有儿子的 $f$,在保证两两匹配数最多的同时,向 $f_i$ 转移尽可能大的值。于是将所有 $f$ 排序贪心找到最大匹配数,然后,二分找到转移给 $f_i$ 的值。

复杂度不太会证,应该接近 $\Theta(n\log n \log \dfrac{\sum{l_i}}{m})$ 吧。

代码

#include 
#define mid ((l+r)>>1)
#define ll long long
#define maxn 50010
using namespace std;
struct Edge{
    int to,next,val;
    Edge(int a=0,int b=0,int c=0){
        to=a,next=b,val=c;
    }
}l[maxn<<1];
int head[maxn],cnt,n,m;
vector son[maxn];
ll f[maxn];
int subans[maxn];
void Add(int a,int b,int c){
    l[++cnt]=Edge(b,head[a],c);
    head[a]=cnt;
}
int check(int u,int pos,int tot,ll x){
    int res=0,l=0;
    for (register int r=tot-1;r;--r){
        r-=r==pos;
        while (l=r) break;
        ++res;++l;
    }
    return res;
}
void Dfs(int u,int fa,ll x){
    f[u]=subans[u]=0;
    son[u].clear();
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa) continue;
        Dfs(v,u,x);
        f[v]+=l[i].val;
        if (f[v]>=x) subans[u]++;
        else son[u].push_back(f[v]);
    }
    int tot=son[u].size();
    sort(son[u].begin(),son[u].end());
    int l=0,r=tot,sub=0,res;
    for (register int r=tot-1;r;--r){
        while (l=r) break;
        ++sub;++l;
    }
    subans[u]+=sub;
    if (sub*2==tot) return;
    l=0,r=tot-1;
    while(l<=r){
        int tem=check(u,mid,tot,x);
        if (tem==sub) res=mid,l=mid+1;
        else r=mid-1;
    }
    f[u]=son[u][res];
}
bool check(ll x){
    int tem=0;
    Dfs(1,0,x);
    for (register int i=1;i<=n;++i)
        tem+=subans[i];
    return tem>=m;
}
int main(){
    ll l=0,r=0,ans,c;
    scanf("%d%d",&n,&m);
    for (register int i=1,a,b;i

本文同步更新于 洛谷博客

Show Comments