[NOIP2018]赛道修建 （树形dp+Multiset）

二分赛道长度。
贪心尽量拼赛道，上传未用到的赛道中最大的一条。
$multiset$开全局应该好一点，就不用吸氧了$QWQ$
但是应该要在所有儿子遍历完之后再循环一次，将所有儿子上传的长度一起丢进$set$。
不然会把儿子和自己的混在一起嘤嘤嘤
二分边界可以再写一个最长链（没必要），也可以用边权$sum/M$.
算$sum$的时候可能会爆$int$。

#include<cstdio>
#include<set> 
using std::multiset;
const int MAXN = 5e4 + 10;
int N, M, cnt, tot = 0;
int h[MAXN];
struct E{
int t, v, nxt;
}Ed[2 * MAXN];
int dfs(int k, int fa, int chk)
{
multiset <int> len;
for (int i = h[k]; i; i = Ed[i].nxt)
{
int u = Ed[i].t;
if (u == fa) continue;
int get = dfs(u, k, chk) + Ed[i].v;
if (get >= chk) cnt++;
else len.insert(get);
}
len.insert(1e8);
multiset <int> :: iterator px, py,i;
int ret = 0;
while (len.size() != 1)
{
px = len.upper_bound(0); int x = *px; len.erase(px);
py = len.lower_bound(chk - x); int y = *py;
if (y != 1e8) cnt++, len.erase(py); else ret = x;
}
return ret;
}
int Solve(int lim)
{
int l = 1, r = lim, ans = 0;
while (l <= r)
{
int mid = (l + r) >> 1; cnt = 0;
dfs(1, -1, mid);
if (cnt >= M) l = mid + 1, ans = mid;
else r = mid - 1;
}
return ans;
}
void Add(int f, int t, int v)
{
Ed[++tot].t = t, Ed[tot].v = v, Ed[tot].nxt = h[f], h[f] = tot;
Ed[++tot].t = f, Ed[tot].v = v, Ed[tot].nxt = h[t], h[t] = tot;
}
int main()
{
scanf("%d%d", &N, &M); long long sum = 0;
for (int i = 1; i < N; i++) {int f, t, v; scanf("%d%d%d", &f, &t, &v); Add(f, t, v); sum += v;}
printf("%dn", Solve((int)(sum / M)));
return 0;
}

最后

以上就是负责小丸子为你收集整理的[NOIP2018]赛道修建 （树形dp+Multiset）的全部内容，希望文章能够帮你解决[NOIP2018]赛道修建 （树形dp+Multiset）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。