UVALive 6584 Escape (Regionals 2013 >> Europe

题目

给出一棵树，每个节点有一个怪物或血药，遇到怪物必须打，打完后扣掉一定的血量。

一开始英雄的血量为\(0\)，当血量小于\(0\)时就挂了。

给出英雄的起点和终点，问能否成功到达终点。

算法

这题的方法真的是太美妙了！感觉ACM的题目比OI的好多了，因为它的程序不长，并且每题都不容易想啊。

我们先来解决一个弱化版问题：把起点作为根，问英雄最多能加多少血。

我们可以想象每个点有一个礼包，这个礼包有两个属性，不妨用\((a,b)\)表示，表示当英雄的血量不少于\(a\)时可以加上\(b\)点血量（\(b\)是负数就减血量）。但是有些限制，如果要取某个礼包，那么它的所有祖先上的礼包都必须先取。

我们现在尝试对每棵子树维护一些礼包，首先要保证所有的礼包都是奖励的。我们不妨假设现在对于点\(v\)，要根据它的所有儿子\(u_i\)的礼包合成点\(v\)子树的礼包。对于点\(v\)，如果它有怪物，我们就要想办法通过提高\(a\)使得\(b\)变为非负数（提高\(a\)是为了取子树的礼包），如果不行，那么这棵子树是不可能走进去的（因为走进去就一定扣血啊）。

通过提高\(a\)的值，现在我们成功地在点\(v\)已经生成了一个礼包，如此下去，我们对于根就生成了一棵礼包树，每个点都是有奖励的！我们就贪心（先选\(a\)最小的）往下走就好了，这个贪心的话，可以用一个左偏树来维护礼包。每开启一个礼包，就把这个礼包的儿子也加进去。

解决了这个弱化版问题后，剩下的就简单了。

代码

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long i64;

const int MAXN = (int) 2e5 + 3;

int n, target;

int A[MAXN];

struct Node{

	Node* s[2];

	int dis;

	i64 minus, plus;

	void init() {

		s[0] = s[1] = NULL;

		dis = 0;

		minus = plus = 0;

	}

};

Node node[MAXN];

struct Edge {

	Edge* next;

	int to;

};

Edge mem[MAXN * 2];

Edge* info[MAXN];

Edge* curMem;

void insert(int a, int b) {

	curMem->to = b;

	curMem->next = info[a];

	info[a] = curMem ++;

}

Node* merge(Node* x, Node* y) {

	if (! x) return y;

	if (! y) return x;

	if (x->minus > y->minus) swap(x, y);

	x->s[1] = merge(x->s[1], y);

	if (x->s[1] ? x->s[1]->dis : 0 > x->s[0] ? x->s[0]->dis : 0)

		swap(x->s[0], x->s[1]);

	x->dis = x->s[1] ? x->s[1]->dis + 1 : 1;

	return x;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);

#endif

	scanf("%*d");

	while (scanf("%d%d", &n, &target) == 2) {

		curMem = mem;

		memset(info, 0, sizeof info);

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

			scanf("%d", A + i);

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

			int v, u;

			scanf("%d%d", &v, &u);

			insert(v, u);

			insert(u, v);

		}

		static int que[MAXN];

		static int fa[MAXN];

		memset(fa, 0, sizeof fa);

		int low = 0, high = 0;

		que[high ++] = target;

		while (low < high) {

			int v = que[low ++];

			for (Edge* pt = info[v]; pt; pt = pt->next) {

				int u = pt->to;

				if (u != fa[v]) {

					fa[u] = v;

					que[high ++] = u;

				}

			}

		}

		static bool path[MAXN];

		memset(path, 0, sizeof path);

		for (int v = 1; v != 0; v = fa[v])

			path[v] = true;

		for (int i = high - 1; i > 0; i --) {

			int v = que[i];

			if (path[v]) continue;

			Node* son = NULL;

			for (Edge* pt = info[v]; pt; pt = pt->next)

				if (! path[pt->to] && pt->to != fa[v])

					son = merge(son, &node[pt->to]);

			Node* cur = node + v;

			cur->init();

			cur->minus = max(0, - A[v]);

			cur->plus = A[v];

			while (son && (cur->plus < 0 || cur->minus > son->minus)) {

				if (cur->plus < 0) {

					cur->minus = max(cur->minus, son->minus - cur->plus);

					cur->plus += son->plus;

				}

				else {

					cur->plus += son->plus;

				}

				son = merge(son->s[0], son->s[1]);

			}

			cur = merge(cur, son);

			if (cur->plus < 0) cur = NULL;

		}

		i64 hp = 0;

		bool ok = true;

		Node* tree = NULL;

		for (int v = 1; v != 0; v = fa[v]) {

			hp += A[v];

			if (hp < 0) {

				ok = false;

				break;

			}

			for (Edge* pt = info[v]; pt; pt = pt->next) {

				int u = pt->to;

				if (path[u]) continue;

				if (u == fa[v]) continue;

				tree = merge(tree, &node[u]);

			}

			while (tree && hp >= tree->minus) {

				hp += tree->plus;

				tree = merge(tree->s[0], tree->s[1]);

			}

		}

		if (ok) printf("escaped\n");

		else printf("trapped\n");

	}

	return 0;

}

巴特西

UVALive 6584 Escape (Regionals 2013 >> Europe - Central)

题目

算法

代码

最新文章

热门文章