CERC2013 Problem E 勇者斗恶龙

地址：http://codeforces.com/gym/100299(要登录了点进gym才能成功传送)
很有意思的一个Problem。

一棵树上，勇者在1号点，初始血量是0。每个点有一个权值，踩上去血量会加上$$delta_i$$，这个值可正可负。勇者任何时候血量不能低于0。问勇者能否到达某个目标点T。
国际惯例$$1 \leq n \leq 10^5, -10^6 \leq delta_i \leq 10^6$$

看了solution以后才写出来的。
其实看之前已经有一些零零碎碎的idea。就是组织不起来。

按道理可以把结果组织成带拓扑关系的pair的形式。pair的第一个元素表示至少要多少血量才能进去，第二个元素表示进去以后能增加多少血量。通俗说就是每个血泉的门槛。
进去以后血量会更亏的地方没有必要走进去
应该转化成最多能获得多少血量的问题。

先看最后一点，转化的方法是从需要到达的点连一条边到一个新的点，这个新的点值是无穷。最后只要看最多能获得的血量是不是达到无穷就行了。

然后剩下的就是solution最神棍的地方。在求解“最多能获得多少血量”的前提下，因为最优性的原则可以把一棵树化归为一种理想结构：拓扑关系为一条链的pair。并且满足上面提到的第2条(即每对pair里加血总比扣血多)，以及依赖越浅的pair，门槛越低。也就是说，把他看成数组的话，门槛递增。

证明分两步。

证明：假设是一条链的依赖关系，那么可以视作以上提到理想结构。
1. 显然一条链上相邻的正值和相邻的负值可以合并。于是必然正负交错，可以构成pair。
2. 依赖关系最深的pair(就是最后一个)，如果first >= second，那么可以直接扔掉。因为根据最优性，永远不会选它。
3. 对于相邻的pair，如果previous.first >= previous.second(扣血比补血多)，那么这个pair必然可以和后面一个合并。原因是根据最优化目标的原则，不可能取了previous就不取next。所以previous和next要么同取要么同不取，所以理应合并。
4. 对于相邻的pair，如果previous.first >= next.first(伤血门槛不递增)，那么previous和next必然可以合并。原因是：根据前面两条，所有的pair都满足first < second，所以根据最优性能取都取掉最好。所以都是贪心去取就好了。如果next门槛比previous还低，那么做完previous肯定顺便做掉next。其实这里条件可以更紧一点，取previous.first >= preivous.first – previous.second + next.first作为合并条件也可以AC的，但是前面那个已经足够了。
证明：假如每个分支下的子树都是链，那么该子树也可以看成链。
其实就是数学归纳法的意思。然后这个只要把每个分支下的pair按first顺序列成一行就可以了。

综上，用multiset<pair <long long, long long>>维护链就可以了。

#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PLL;
typedef multiset <PLL> MS;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
const int N = 200005;
const ll INF = 1e15;
int Tc, n, m;
vector <int> E[N];
MS pool[N];
ll a[N];

MS* merge(MS *a, MS *b) {
    if (a->size() < b->size()) swap(a, b);
    foreach (it, *b) a->insert(*it);
    b->clear();
    return a;
}

MS* dfs(int u, int fa) {
    MS *res = &pool[u];
    rep (i, E[u].size())
        if (E[u][i] != fa)
            res = merge(dfs(E[u][i], u), res);
    PLL cur = a[u] > 0 ? PLL(0, a[u]) : PLL(-a[u], 0);
    while (!res->empty() && (cur.second < cur.first || cur.second >= res->begin()->first)) {
        PLL tmp = *res->begin();
        res->erase(res->begin());
        cur = tmp.first > cur.second ? PLL(cur.first - cur.second + tmp.first, tmp.second) : PLL(cur.first, cur.second - tmp.first + tmp.second);
    }
    if (cur.second > cur.first) res->insert(cur);
    return res;
}

int main() {
    scanf("%d", &Tc);
    while (Tc--) {
        scanf("%d%d", &n, &m);
        rep (i, n + 1) E[i].clear();
        rep (i, n) {
            int x;
            scanf("%d", &x);
            a[i] = x;
        }
        rep (i, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--; v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }
        --m;
        E[m].push_back(n);
        E[n].push_back(m);
        a[n++] = INF;
        MS *res = dfs(0, -1);
        ll hp = 0;
        bool flag = 0;
        foreach (it, *res) if (hp >= it->first) {
            hp += it->second - it->first;
            if (hp >= INF / 2) flag = 1;
        }
        res->clear();
        puts(flag ? "escaped" : "trapped");
    }
    return 0;
}

CERC2013 Problem E 勇者斗恶龙

留下评论

取消回复