首页 > Web开发 > 详细

Uva LA 3902 - Network 树形DP 难度: 0

时间:2019-02-17 16:05:10      阅读:264      评论:0      收藏:0      [点我收藏+]

题目

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1903


题意

一棵树,根上有VOD站,要求任意叶节点到VOD站的距离不超过k,问最少建新VOD站数。

 

思路

1. 令vod[i]为节点i到VOD站的最短距离,  注意,这是在以i为根的树上有VOD站的情况下,如果没有,vod[i]就设为非法。

依据树形DP的思路,如果在该节点(非叶节点)建站,vod[i]=0,否则 vod[i] = min(vod[child] + 1) for child in i.children.(此时注意不要统计没有VOD的子树的非法值)

2. 令urge[i]为以i为根的树中有叶节点还没被满足的情况下,该节点能忍受VOD站在此树外的最远距离。注意如果所有叶节点都被满足了,urge[i]就设为非法。

对于叶节点, urge[i] = k,对于非叶节点,urge[i] = min(urge[child] + 1] for child in i.children),(此时注意不要统计已经被满足的非法值)

3. 如何判断这棵树的孩子们之间有没有相互满足?明显,如果urge[i]和vod[i]都存在,且urge[i] <= vod[i],则说明有兄弟相互满足的情况。

4. 如果孩子们之间无法相互满足?如果urge[i] > 0,说明不紧迫,交给父亲树去办。如果urge[i] = 0,说明需要建新站。

 

感想

1. 注意边是无向边,因此边数是点数2倍!

 

代码

技术分享图片
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 2e3 + 4;
const int inf = 0x3ffffff;
int n, k, s;
int vod[MAXN];
int urge[MAXN];
int first[MAXN];
int to[MAXN];
int nxt[MAXN];
int edgeNum;

void addEdge(int f, int t) {
    nxt[edgeNum] = first[f];
    to[edgeNum] = t;
    first[f] = edgeNum++;
}

int dfs(int root, int fa) {
    if (nxt[first[root]] == -1) {
        urge[root] = k;
        vod[root] = inf;
        return 0;
    }
    int ans = 0;
    vod[root] = inf;
    urge[root] = inf;
    for (int p = first[root]; p != -1; p = nxt[p]) {
        int t = to[p];
        if (t == fa)continue;
        ans += dfs(t, root);
        if (vod[t] != inf) {
            vod[root] = min(vod[t] + 1, vod[root]);
        }
        if (urge[t] != inf) {
            urge[root] = min(urge[t] - 1, urge[root]);
        }
    }
    if (urge[root] != inf) {
        if (vod[root] != inf && vod[root] <= urge[root]) {
            urge[root] = inf;//satisfied
        }
        else if (urge[root] == 0 && root != s) {
            ans ++;
            vod[root] = 0;//set up a new one;
            urge[root] = inf;//satisfied
        }
    }
    return ans;
}


int main() {
#ifdef LOCAL_DEBUG
    freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
    //freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
    int T;
    scanf("%d", &T);
    for (int ti = 1; ti <= T; ti++) {
        memset(first, -1, sizeof first);
        edgeNum = 0;
        scanf("%d%d%d", &n, &s, &k);
        for (int i = 1; i < n; i++) {
            int f, t;
            scanf("%d%d", &f, &t);
            addEdge(f, t);
            addEdge(t, f);
        }
        int ans = dfs(s, -1);
        printf("%d\n", ans);
        
    }

    return 0;
}
View Code

 

Uva LA 3902 - Network 树形DP 难度: 0

原文:https://www.cnblogs.com/xuesu/p/10391343.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!