BZOJ 5174: [JSOI2013]哈利波特与死亡圣器 – [二分/树形DP]


题目传送门(BZOJ)
>原文链接<

题意 :

由于这题题面太长了, 还是说一下题意吧 :

Bob和Ailce两个人玩游戏, Bob从一号点出发, 可以用一个单位时间走到下一个点.

Alice可以购买派出数量的小人来对剩下的节点染色, 要求使Bob每走到一个点都一定是被染色了的点

问要达成目标, 最多的一次最少派出多少小人 ?

题解 :

鲜明的二分标志, 考虑二分答案.

首先Bob的路径一定是从根到一个叶子, 回头路只会给Alice更多时间

而对于Bob到的每个节点, Alice必须要把它的所有儿子提前染好.

首先预处理出来每个节点的儿子数量son[p]

设状态F[p]是Bob走到p点, p的儿子有多少个需要p的祖先用多余的小人染色.

得到转移F[p]=son[p]-mid+\sum\limits_{fa[v]=p}F[v]

并且这个节点多余的小人不能对祖先产生贡献, 所以返回的时候F[p]要和0取个\max

F[1]=0,代表当前解足够染色, 否则不够

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2; const int N = 310000;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
struct Edge {
    int to;
    Edge *next;
}*h[N], e[N<<1];
inline void addEdge(int u, int v) {
    static int _;
    Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;
}
int son[N], f[N], mid;
void getSon(int p, int fa) {
    rev(i, p) if(i->to != fa) {
        son[p] ++ ;
        getSon(i->to, p);
    }
}
void getAns(int p, int fa) {
    f[p] = son[p]-mid;
    rev(i, p) if(i->to != fa) {
        getAns(i->to, p);
        f[p] += f[i->to];
    }
    f[p] = max(0, f[p]);
}
int main() {
    int n = rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = rd(), v = rd();
        addEdge(u, v);
        addEdge(v, u);
    }
    getSon(1, 0);
    int l = 0, r = n, ans = 0;
    while(l <= r) {
        mid = (l+r) >> 1;
        getAns(1, 0);
        if(!f[1]) ans = mid, r = mid-1;
        else l = mid+1;
    }
    printf("%d\n", ans);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注