「APIO2012」派遣

传送门

当预算超过限制时，优先丢掉薪水高的忍者（左偏树维护一下），然后答案取合法答案的最大值。

参考代码：

#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

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

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

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

typedef long long LL;

const int _ = 1e5 + 5;

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

inline void Add_edge(int u, int v)

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

int n, m, rt, c[_], l[_], siz[_]; LL sum[_], ans;

int tr[_], dis[_], lc[_], rc[_];

inline int merge(int x, int y) {

	if (!x || !y) return x + y;

	if (c[x] < c[y]) swap(x, y);

	rc[x] = merge(rc[x], y);

	if (dis[lc[x]] <  dis[rc[x]]) swap(lc[x], rc[x]);

	dis[x] = dis[rc[x]] + 1;

	return x;

}

inline void dfs(int u, int f) {

	siz[u] = 1, sum[u] = c[u], tr[u] = u;

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

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

		dfs(v, u), siz[u] += siz[v], sum[u] += sum[v], tr[u] = merge(tr[u], tr[v]);

	}

	while (sum[u] > m)

		sum[u] -= c[tr[u]], --siz[u], tr[u] = merge(lc[tr[u]], rc[tr[u]]);

	ans = max(ans, 1ll * siz[u] * l[u]);

}

int main() {

	read(n), read(m);

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

		read(f), read(c[i]), read(l[i]);

		if (!f) rt = i; else Add_edge(f, i);

	}

	dfs(1, 0);

	printf("%lld\n", ans);

	return 0;

}

巴特西

「APIO2012」派遣

「APIO2012」派遣

最新文章

热门文章