「NOIP2018」赛道修建

题目链接:LOJ2952

Description

给定一棵带权树,现在请你将这棵树中选出$m$条不相交的链,每一条链的权值就是这条链上所有边的边权之和。
现在请你给出一种方案,让选出的$m$条链中最小的权值最大。

Data Range

$1\leq n\leq 5\times 10^4,1\leq m\leq n-1,1\leq a_i,b_i\leq n, 1\leq l_i \leq 10^4$

Solution

题目中出现了最小的最大或者最大的最小的关键词,所以我们考虑二分答案。
关于二分查找的$check$,我们就是$check$有多少条长度$\geq mid$
因为每一个条边最多只能被选择一次,那么这条路径经过$u$号节点的情况一共有两种,一种是一端为$u$号节点,另一端为$v$子树内的一个节点,另一种为一段在$v1$子树中,另一端在$v2$子树中,而且经过了$u$号节点,我们将这两种情况分开来讨论。
我们再一次转化题意:现在给定若干条路径,长度给定,请你最大化两两拼接或者单独一条能够长度$\geq value$的条数,$value$给定。
我们将问题在树上划分成若干个子问题,每一个子问题的对象是$u$号节点。
考虑到$u->v$这样一条边只能出现在一条选择的路径中,所以我们假设$v$子树内已经有了一部分被选择了,有一部分还未被选择,我们最优的策略肯定是选择还未被选择的路径中一个端点在$v$上的最长的一段,然后再加上一个$u->v$的长度。
如果在我们已经选择的路径中已经出现了长度$\geq mid$的话,就表示这些路径可以被选择了,这样不会影响到我们当前的决策。
以上我们已经解决了第一种情况的所有答案。
考虑剩下来还未被选择的路径,现在这些路径一段的端点都是$u$节点了,对于每一条路径长度为$value$,我们二分查找出另外一条$\geq mid-value$,如果存在,那么就匹配并且删除原来的边和现在匹配的边,否则就删除原来的边。

Code

#include <bits/stdc++.h>

using namespace std;

template <typename T> void read(T &x) {
  x = 0; char ch = 0; bool flg = 0;
  for (; !isdigit(ch); ch = getchar()) flg |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  flg ? x *= -1 : 233;
}

const int N = 5e4 + 5;

vector<pair<int, long long> > G[N];
int n, m, tot;
long long sum = 0, need;

long long dfs(int u, int _fa) {
  multiset<long long> st;
  for (auto& v : G[u]) {
    if (v.first == _fa) continue;
    long long dis = dfs(v.first, u) + v.second;
    if (dis >= need) {
      tot++;
    } else {
      st.insert(dis);
    }
  }
  long long mx = 0;
  while (st.size()) {
    long long _d = *st.begin();
    st.erase(st.begin());
    multiset<long long>::iterator it = st.lower_bound(need - _d);
    if (it == st.end()) {
      mx = max(mx, _d);
    } else {
      st.erase(it);
      tot++;
    }
  }
  return mx;
}

bool check(long long x) {
  need = x;
  tot = 0;
  dfs(1, 0);
  return tot >= m;
}

int main() {
  freopen("track.in", "r", stdin);
  freopen("track.out", "w", stdout);
  read(n); read(m);
  for (int i = 1; i < n; i++) {
    int u, v;
    long long w;
    read(u); read(v); read(w);
    G[u].push_back({v, w});
    G[v].push_back({u, w});
    sum += w;
  }
  long long l = 0, r = sum, ans = 0;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (check(mid)) {
      l = mid + 1; 
      ans = mid; 
    } else {
      r = mid - 1;
    }
  }
  printf("%lld\n", ans);
  return 0; 
}
最后修改:2019 年 09 月 07 日 08 : 08 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论