吉吉王国

NC210473. 吉吉王国

描述

吉吉王国有 $n$ 个城市，其中 $1$ 号城市就是吉吉王国的首都，并且吉吉王国有 $n-1$ 条道路，每条道路都有一个长度 $d$ ，你可以从任意一点 $u$ 到达任意一点 $v$ 。但是最近吉吉王国发生了动乱，除了首都外，每个只有一条道路连向的城市出现了反叛军。

这些城市的反叛军开始向吉吉王国的首都发起了进攻，如果让他们到达首都，那么吉吉国王就要换人了。吉吉国王现在需要快速切断一些道路，使得没有一个城市的反叛军可以到达首都。但是由于物资的限制，他能切断的道路的总长度和不能超过 $m$ ，并且要保证切断道路尽量快，因此切断的道路中最长的长度要尽可能小。

现在赶紧告诉吉吉国王切断的道路的最长长度在最小的时候是多少吧。

输入描述

第一行两个整数。
接下来行每行三个整数表示城市和城市有一条长度为的道路。

输出描述

如果存在方案使得首都安全，输出最小的最长长度，否则输出-1。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 444K, 提交时间: 2021-09-27 19:44:21

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+1;
int n, m;
vector<pair<int, int>> G[MAXN];
int x;
long long dfs(int s, int f) {
  if (s != 1 && G[s].size() == 1) return 0x3f3f3f3f;
  long long ans = 0;
  for (auto [t, d]: G[s]) if (t != f) {
    ans += min(d<=x?d:0x3f3f3f3fll, dfs(t, s));
  }
  return ans;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int x, y, z; cin >> x >> y >> z;
    G[x].push_back({y, z});
    G[y].push_back({x, z});
  }
  int ans = dfs(1, 0);
  int lo = 0, hi = 0x3f3f3f3f;
  while (lo < hi) {
    x = (lo+hi)/2;
    if (dfs(1, 0) <= m) hi = x;
    else lo = x+1;
  }
  if (hi == 0x3f3f3f3f) cout << -1 << endl;
  else cout << lo << endl; 
}