洛谷 P5021 [NOIP2018]赛道重建

传送门

思路

思路就是常规的思路，所以就不说了……我就是来记录一下我的\(AC\)之路的，真的是太爽了

洛谷 P5021 [NOIP2018]赛道重建-LMLPHP

没错……我也是一个个打的部分分，最后终于AC的，至于为什么中间又会有\(35\)、\(25\)、\(0\)这样的分数……纯粹是因为我犯了zz错误……

代码

1、\(b_i = a_i + 1\) 链的情况

#include <bits/stdc++.h>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

const int N = 50011;

int a[N], n, m, cnt, head[N], sum;

struct node {

	int to, nxt, val;

} e[N << 1];

inline void add(int from, int to, int w) {

	e[++cnt].to = to;

	e[cnt].val = w;

	e[cnt].nxt = head[from];

	head[from] = cnt;

}

void dfs(int x, int fa) {

	for(int i = head[x]; i ; i = e[i].nxt) {

		int y = e[i].to;

		if(y == fa) continue;

		dfs(y, x);

		a[x] = e[i].val;

	}

}

int check(int k) {

	int t = 0, now = 1;

	for(int i = 1; i < n; i++) {

		if(now + a[i] >= k) {

			now = 0;

			t++;

		}

		else now += a[i];

	}

	return t >= m;

}

int main() {

	n = read(), m = read();

	for(int i = 1; i < n; i++) {

		int u = read(), v = read(), w = read();

		add(u, v, w);

		add(v, u, w);

		sum += w;

	}

	dfs(1, 0);

	int l = 1, r = sum, mid;

	while(l < r) {

		mid = (l + r) >> 1;

		if(check(mid)) l = mid;

		else r = mid - 1;

	}

	cout << l << '\n';

}

2、\(m = 1\) 求树的直径

#include <bits/stdc++.h>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

const int N = 50011;

int a[N], n, m, cnt, head[N], sum, ans;

struct node {

	int to, nxt, val;

} e[N << 1];

inline void add(int from, int to, int w) {

	e[++cnt].to = to;

	e[cnt].val = w;

	e[cnt].nxt = head[from];

	head[from] = cnt;

}

int dfs(int x,int fa) {

	int sum1 = 0, sum2 = 0;

	for(int i = head[x]; i; i = e[i].nxt) {

		int y = e[i].to;

		if(y == fa) continue;

		sum2 = max(sum2, dfs(y, x) + e[i].val);

		if(sum2 > sum1) swap(sum1, sum2);

	}

	ans = max(ans, sum1 + sum2);

	return sum1;

}

int main() {

	n = read(), m = read();

	for(int i = 1; i < n; i++) {

		int u = read(), v = read(), w = read();

		add(u, v, w);

		add(v, u, w);

		sum += w;

	}

	dfs(1, 0);

	cout << ans << '\n';

}

3、\(a_i = 1\) 菊花图

#include <bits/stdc++.h>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

const int N = 50011;

const int inf = 0x3f3f3f3f;

int a[N], n, m, cnt, head[N], sum, ans;

struct node {

	int to, nxt, val;

} e[N << 1];

inline void add(int from, int to, int w) {

	e[++cnt].to = to;

	e[cnt].val = w;

	e[cnt].nxt = head[from];

	head[from] = cnt;

}

bool cmp(int a, int b) {

	return a > b;

}

int main() {

	n = read(), m = read();

	for(int i = 1; i < n; i++) {

		int u = read(), v = read(), w = read();

		add(u, v, w);

		add(v, u, w);

		sum += w;

	}

	for(int i = head[1], y; i; i = e[i].nxt) {

		y = e[i].to;

		a[y - 1] = e[i].val;

	}

	sort(a + 1, a + n, cmp);

	int ans = inf;

	for(int i = 1; i <= m; i++)

		ans = min(ans, a[i] + a[2 * m - i + 1]);

	cout << ans << '\n';

	return 0;

}

4、混起来的部分分

#include <bits/stdc++.h>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

const int N = 50011;

const int inf = 0x3f3f3f3f;

int a[N], n, m, cnt, head[N], sum, ans;

struct node {

	int to, nxt, val;

} e[N << 1];

inline void add(int from, int to, int w) {

	e[++cnt].to = to;

	e[cnt].val = w;

	e[cnt].nxt = head[from];

	head[from] = cnt;

}

namespace subtask1 {

	int a[N];

	void dfs(int x, int fa) {

		for(int i = head[x]; i ; i = e[i].nxt) {

			int y = e[i].to;

			if(y == fa) continue;

			dfs(y, x);

			a[x] = e[i].val;

		}

	}

	int check(int k) {

		int t = 0, now = 1;

		for(int i = 1; i < n; i++) {

			if(now + a[i] >= k) {

				now = 0;

				t++;

			} else now += a[i];

		}

		return t >= m;

	}

	void solve() {

		dfs(1, 0);

		int l = 1, r = sum, mid;

		while(l < r) {

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

			if(check(mid)) l = mid;

			else r = mid - 1;

		}

		cout << l << '\n';

	}

}

namespace subtask2 {

	int dfs(int x,int fa) {

		int sum1 = 0, sum2 = 0;

		for(int i = head[x]; i; i = e[i].nxt) {

			int y = e[i].to;

			if(y == fa) continue;

			sum2 = max(sum2, dfs(y, x) + e[i].val);

			if(sum2 > sum1) swap(sum1, sum2);

		}

		ans = max(ans, sum1 + sum2);

		return sum1;

	}

	void solve() {

		dfs(1, 0);

		cout << ans << '\n';

	}

}

namespace subtask3 {

	bool cmp(int a, int b) {

		return a > b;

	}

	void solve() {

		for(int i = head[1], y; i; i = e[i].nxt) {

			y = e[i].to;

			a[y - 1] = e[i].val;

		}

		sort(a + 1, a + n, cmp);

		int ans = inf;

		for(int i = 1; i <= m; i++)

			ans = min(ans, a[i] + a[2 * m - i + 1]);

		cout << ans << '\n';

	}

}

int main() {

	n = read(), m = read();

	int flag = 1, f = 1;

	for(int i = 1; i < n; i++) {

		int u = read(), v = read(), w = read();

		add(u, v, w);

		add(v, u, w);

		if(u != 1) flag = 0;

		if(v != u + 1) f = 0;

		sum += w;

	}

	if(flag) {

		subtask3::solve();

	}

	else if(f){

		subtask1::solve();

	}

	else {

		subtask2::solve();

	}

	return 0;

}

5、正解！！（\(multiset\)）

#include <bits/stdc++.h>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

const int N = 50011;

const int inf = 0x3f3f3f3f;

int a[N], n, m, cnt, head[N], ans, up;

struct node {

	int to, nxt, val;

} e[N << 1];

multiset<int> s[N];

multiset<int>::iterator it;

inline void add(int from, int to, int w) {

	e[++cnt].to = to;

	e[cnt].val = w;

	e[cnt].nxt = head[from];

	head[from] = cnt;

}

int dfs(int x, int fa, int k) {

	s[x].clear();

	int w;

	for(int i =  head[x]; i; i = e[i].nxt) {

		int y = e[i].to;

		if(y == fa) continue;

		w = dfs(y, x, k) + e[i].val;

		if(w >= k) ans++;

		else s[x].insert(w);

	}

	int maxn = 0;

	while(!s[x].empty()) {

		if(s[x].size() == 1) {

			return max(maxn, *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()) {

			maxn = max(maxn, *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 maxn;

}

int dfs1(int x,int fa) {

	int sum1 = 0, sum2 = 0;

	for(int i = head[x], y; i; i = e[i].nxt) {

		y=e[i].to;

		if(y == fa) continue;

		sum2 = max(sum2, dfs1(y, x) + e[i].val);

		if(sum1 < sum2) swap(sum1, sum2);

	}

	up = max(up, sum1 + sum2);

	return sum1;

}

int check(int k) {

	ans = 0;

	dfs(1, 0, k);

	if(ans >= m) return 1;

	return 0;

}

int main() {

	n = read(), m = read();

	for(int i = 1; i < n; i++) {

		int u = read(), v = read(), w = read();

		add(u, v, w);

		add(v, u, w);

	}

	dfs1(1, 0);

	int l = 1, r = up, mid;

	while(l < r) {

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

		if(check(mid)) l = mid;

		else r = mid - 1;

	}

	cout << l << '\n';

}