[ZJ][一年後修正版][樹型DP] b174. 旅游规划＠Morris' Blog

2012-12-02 16:55:03| 人氣630| 回應0 | 上一篇 | 下一篇

[ZJ][一年後修正版][樹型DP] b174. 旅游规划

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

W市的交通规划出现了重大问题，市政府下决心在全市的各大交通路口安排交通疏导员来疏导密集的车流。但由于人员不足，W市市长决定只在最需要安排人员的路口安放人员。具体说来，W市的交通网络十分简单，它包括n个交叉路口和n-1条街道，任意一条街道连接两个交叉路口，并且任意两个交叉路口之间都存在一条路径互相连接。经过长期调查结果显示如果一个交叉路口位于W市交通网的最长路径上，那么这个路口必然拥挤不堪，所谓最长路径定义为某条路径p=(v1,v2,v3…vk)，路径经过的路口各不相同且城市中不存在长度>k的路径（因此可能存在着不唯一的最长路径）。因此W市市长希望知道有哪些路口位于城市交通网的最长路径之上。

輸入說明：

第一行包括一个整数n。

之后的n-1行每行包括两个整数u, v表示编号为u和v的路口之间存在着一条街道（注意：路口被依次编号为0到n-1）

輸出說明：

输出包括若干行，每行包括一个整数——某个位于最长路上路口的编号。

为了确保解唯一，我们规定位于所有最长路上的路口按编号顺序从小到大输出。

範例輸入：

範例輸出：

提示：

说明：
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000

出處：

2008 海峽兩岸青少年程式設計競賽

做法 : 兩次 dfs,
1st dfs :
得到由下而上的最大高度 (要記錄第一高第二高),
意即得到每個節點的 subtree 的高度
2nd dfs :
將父節點高度轉過來, 這時要注意, 如果第一高是從這個節點接上去的, 那麼就抓第二高+1,

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
unsigned short dp1[200000][2], dp2[200000];
vector<int> g[200000];
void dfs1(int nd, int p) {
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(*it != p) {
            dfs1(*it, nd);
            if(dp1[*it][0]+1 > dp1[nd][1])
                dp1[nd][1] = dp1[*it][0]+1;
            if(dp1[nd][0] < dp1[nd][1])
                swap(dp1[nd][0], dp1[nd][1]);
        }
    }
}
void dfs2(int nd, int p) {
    if(nd) {
        if(dp1[nd][0]+1 == dp1[p][0])
            dp2[nd] = max(dp1[p][1], dp2[p])+1;
        else
            dp2[nd] = max(dp1[p][0], dp2[p])+1;
    }
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(*it != p)
            dfs2(*it, nd);
    }
}
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, i, x, y;
    scanf("%d", &n);
    for(i = 1; i < n; i++) {
        ReadInt(&x);
        ReadInt(&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    int longest = 0;
    for(i = 0; i < n; i++) {
        longest = max(longest, dp1[i][0]+dp1[i][1]);
        longest = max(longest, dp1[i][0]+dp2[i]);
    }
    for(i = 0; i < n; i++) {
        if(longest == dp1[i][0]+dp1[i][1] ||
           longest == dp1[i][0]+dp2[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

我要檢舉

#b174#旅游规划#樹型DP

台長： Morris

您可能對以下文章有興趣

b109. 2. IC 板檢測

b058. 3. 關鍵邏輯閘

[ZJ][模擬水] a349. 2. 指令解譯器

[ZJ][BIT] a484. 美麗風景遞增之路

人氣(630) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][zkw線段樹] d801. SCOI2006 2.动态最值(minmax)
此分類上一篇:[ZJ][BFS] d373. 5. 乳酪的誘惑

回應(0)