noip2018 D1T3 赛道修建

题目描述

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 = ;

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 = ;

    while(!s[now].empty())

    {

        if(s[now].size() == ) return max(Max,*s[now].begin());

        it = s[now].lower_bound(k-*s[now].begin());

        if(it == s[now].begin()&&s[now].count(*it) == ) 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 = ;

    dfs1(,,k);

    if(ans >= m) return true;

    else return false;

}

int main(){

    scanf("%d%d",&n,&m);

    int u , v , w;

    for(int i = ;i <= n - ;i++)

    {

      scanf("%d%d%d",&u,&v,&w);

      add(u ,v , w);

      add(v , u ,w);

    }

    dfs(,,);  //

    dfs(gd,,);  // 两遍dfs求树的直径

    int  l = ,r = zj;

    while(l < r)

    {

        int mid = (l + r + ) >> ;

        if(check(mid)) l = mid;

        else r = mid - ;

    }

    printf("%d",l);

}

巴特西

noip2018 D1T3 赛道修建

题目描述

输入输出格式

最新文章

热门文章