「NOIP2018」赛道修建

传送门

Luogu

解题思路

一眼先二分（上界树的直径，下界最小边权），然后再考虑 \(\text{DP}\)。

对于当前节点 \(u\)，在它的所有儿子中分别返回一条匹配不完的长度最大的路径 \(Max\)。

若该路径长大于二分值，直接修一条，不然丢进 \(\text{multiset}\) 里面。

对于 \(\text{multiset}\) 里的元素每次贪心的找出尽可能大的一条与最小的匹配，若找不到则用来更新 \(Max\)

\(check\) 函数里面返回 \(ans\ge m\)，最后输出答案即可。

细节注意事项

\(\text{multiset}\) 的使用要熟练

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <set>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 50010;

const int __ = 100010;

int tot, head[_], nxt[__], ver[__], w[__];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, w[tot] = d; }

int n, m, ans;

multiset < int > S[_];

multiset < int > ::iterator it;

inline int dfs(int u, int f, int mid) {

	S[u].clear();

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		int res = dfs(v, u, mid) + w[i];

		if (res >= mid) ++ans; else S[u].insert(res);

	}

	int _max = 0;

	while (!S[u].empty()) {

		if (S[u].size() == 1)

			return _max = max(_max, *S[u].begin());

		it = S[u].lower_bound(mid - *S[u].begin());

		if (it == S[u].begin() && S[u].count(*it) == 1) ++it;

		if (it == S[u].end()) {

			_max = max(_max, *S[u].begin());

			S[u].erase(S[u].find(*S[u].begin()));

		} else {

			++ans;

			S[u].erase(S[u].find(*it));

			S[u].erase(S[u].find(*S[u].begin()));

		}

	}

	return _max;

}

inline bool check(int mid)

{ ans = 0, dfs(1, 0, mid); return ans >= m; }

int _min = 100000, _max, id;

inline void dfs_d(int u, int f, int sum) {

	if (sum > _max) _max = sum, id = u;

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		_min = min(_min, w[i]), dfs_d(v, u, sum + w[i]);

	}

}

inline void get_d() { dfs_d(1, 0, 0), _max = 0, dfs_d(id, 0, 0); }

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n), read(m);

	for (rg int u, v, d, i = 1; i < n; ++i)

		read(u), read(v), read(d), Add_edge(u, v, d), Add_edge(v, u, d);

	get_d();

	int l = _min, r = _max;

	while (l < r) {

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

		if (check(mid)) l = mid;

		else r = mid - 1;

	}

	printf("%d\n", l);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「NOIP2018」赛道修建

解题思路

细节注意事项

参考代码

最新文章

热门文章