「NOIp2018」赛道修建-贪心+二分

题目描述

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\) 条赛道中最短赛道的长度尽可能大)

Links

Luogu P5021

Solution

观察题目可知,这道题肯定是二分("你的任务是设计一种赛道修建的方案,使得修建的 \(m\) 条赛道中长度最小的赛道长度最大(即 \(m\) 条赛道中最短赛道的长度尽可能")

显然二分的是这\(m\) 条赛道中长度最小的赛道的长度,我们设它为\(k\) 。考虑check。

对于每个结点,我们先访问它的子结点,将它的子结点上传的所有链的长度放进一个multiset。那么有两种情况

  • 传上来的某条链本身长度就比\(k\)大,显然这时候再往上面连边无非是浪费边,直接给答案+1即可
  • 传上来的某两条链合并起来的长度比\(k\)大,那么对于处理完第一种情况的所有链,每次取出其中最短的链,找到第一个和它连起来比\(k\)大的值,把它们连起来(即在multiset中删去),最后上传剩余链中最大者

Code

#include 
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair pii;

template  inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template  inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template  inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const int maxn = 50000 + 5;

int n,m,ans = 0,sum1 = 0;
int head[maxn],cnt;

multiset  s[maxn];
multiset  :: iterator it;

struct edge{
    int to;
    int next;
    int w;
}e[maxn << 1];

void add_edge(int u,int v,int w){
    cnt++;
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

int dfs(int x,int fa,int k){
    s[x].clear();
    int sum;
    for(int i = head[x]; i; i = e[i].next){
        int y = e[i].to;
        if(y == fa) continue;
        sum = dfs(y,x,k) + e[i].w;
        if(sum >= k){
            ans++;//第一种情况
        }else s[x].insert(sum);
    }
    int maxium = 0;
    while(!s[x].empty()){
        if(s[x].size() == 1) return max(maxium,*s[x].begin());//上传最长者
        it = s[x].lower_bound(k - *s[x].begin());
        if(it == s[x].begin() && s[x].count(*it) == 1) it++;//如果搜到了最短的链本身且这个长度的链有且只有一条,向后移动迭代器
        if(it == s[x].end()){//若没有找到比k-*s[x].begin()大的,就取个最大值,把*s[x].begin()删掉
            Chkmax(maxium,*s[x].begin());
            s[x].erase(s[x].find(*s[x].begin()));
        }else{
            ans++;
            s[x].erase(s[x].find(*it));
            s[x].erase(s[x].find(*s[x].begin()));
        }//第二种情况
    }
    return maxium;//把剩余的最长链上传给父亲
}

bool check(int k){
    ans = 0;
    dfs(1,0,k);
    if(ans >= m) return true;
    return false;
}

inline void Solve (){
    int l = 1,r = sum1;//显然最长链也不会比所有链的长度和长
    int mid;
    while(l < r){
        mid = (l + r + 1) >> 1;
        if(check(mid)){
            l = mid;
        }else r = mid - 1;
    }
    printf("%d\n",l);
}

inline void Input (){
    n = read();
    m = read();
    for(int i = 1; i <= n - 1; i++){
        int x,y,z;
        x = read();
        y = read();
        z = read();
        sum1 += z;
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
}

int main(){
    Input();
    Solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注