首页 > 搜索 > DFS搜索 > HDU 4679-Terrorist’s destroy-DFS-[解题报告]HOJ
2015
09-17

HDU 4679-Terrorist’s destroy-DFS-[解题报告]HOJ

Terrorist’s destroy

问题描述 :

There is a city which is built like a tree.A terrorist wants to destroy the city’s roads. But now he is alone, he can only destroy one road, then the city will be divided into two cities. Impression of the city is a number defined as the distance between the farthest two houses (As it relates to the fare).When the terrorist destroyed a road, he needs to spend some energy, assuming that the number is a.At the same time,he will get a number b which is maximum of the Impression of two cities. The terrorist wants to know which road to destroy so that the product of a and b will be minimized.You should find the road’s id.
Note that the length of each road is one.

输入:

The first line contains integer T(1<=T<=20), denote the number of the test cases.
For each test cases,the first line contains a integer n(1 < n <= 100000);denote the number of the houses;
Each of the following (n-1) lines contains third integers u,v,w, indicating there is a road between house u and houses v,and will cost terrorist w energy to destroy it.The id of these road is number from 1 to n-1.(1<=u<=n , 1<=v<=n , 1<=w<=10000)

输出:

The first line contains integer T(1<=T<=20), denote the number of the test cases.
For each test cases,the first line contains a integer n(1 < n <= 100000);denote the number of the houses;
Each of the following (n-1) lines contains third integers u,v,w, indicating there is a road between house u and houses v,and will cost terrorist w energy to destroy it.The id of these road is number from 1 to n-1.(1<=u<=n , 1<=v<=n , 1<=w<=10000)

样例输入:

2
5
4 5 1
1 5 1
2 1 1
3 5 1
5
1 4 1
1 3 1
5 1 1
2 5 1

样例输出:

Case #1: 2
Case #2: 3

给一棵树,每条边上都有一个权值,去掉树上任意一条边之后,分成两个子树,两个子树的最长路与这条边上的权值相乘,的到一个乘积。问去掉那一条边可以使这个乘积最小。

首先找到树上的最长路,那么删边的时候有两种情况:

1. 这条边不是最长路上的边

2. 这条边是最长路上的边

对于第一种情况,很容易计算出乘积。

对于第二种情况,只需要计算出被分成的两个子树里面的最长路径长度即可,这个可以预处理一下。分析可以发现,这种情况下,两棵子树的最长路,一定是以整棵树的最长路的两个端点为起始点的,因此只需要预处理出所有点到两个端点的距离,然后根据删除的最长路边求两颗子树中的最大值即可。

所有预处理都是dfs……

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 100010
#define inf 0x7fffffff

bool y[N];
int n, s, t, ds[N], dt[N], ms[N], mt[N], len, id, ans;
struct node {
    int v, w, id;
    node() {}
    node(int _v, int _w, int _id) : v(_v), w(_w), id(_id) {}
};
vector<node> g[N];
void dfs(int now, int fa) {
    int u;
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].v) != fa) {
            ds[u] = ds[now] + 1;
            dfs(u, now);
        }
}
void dfs2(int now, int fa) {
    int u;
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].v) != fa) {
            dt[u] = dt[now] + 1;
            dfs2(u, now);
        }
}
void d1(int now, int fa) {
    int u;
    mt[now] = dt[now];
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].v) != fa) {
            d1(u, now);
            mt[now] = max(mt[now], mt[u]);
        }
}
void d2(int now, int fa) {
    int u;
    ms[now] = ds[now];
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].v) != fa) {
            d2(u, now);
            ms[now] = max(ms[now], ms[u]);
        }
}
void work(int now, int fa) {
    int u, w;
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].v) != fa) {
            if (ds[now] + 1 + dt[u] == len)
                w = g[now][i].w * max(ms[now], mt[u]);
            else w = g[now][i].w * len;

            if (w < ans) { ans = w, id = g[now][i].id; }
            else if (w == ans && g[now][i].id < id)
                id = g[now][i].id;
            work(u, now);
        }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int size = 20 << 20; // 20MB
    char *p = (char*)malloc(size) + size;
    __asm__("movl %0, %%esp\n" :: "r"(p));

    int T;
    scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        scanf("%d", &n);
        for (int i=0; i<=n; i++) {
            g[i].clear();
            y[i] = false;
        }
        for (int i=1, a, b, c; i<n; i++) {
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(node(b, c, i));
            g[b].push_back(node(a, c, i));
        }
        ds[1] = 0;
        dfs(1, 0);
        ds[s=0] = 0; for (int i=1; i<=n; i++) if (ds[i] > ds[s]) s = i;

        ds[s] = 0; dfs(s, 0);
        t = 0; for (int i=1; i<=n; i++) if (ds[i] > ds[t]) t = i;
        len = ds[t];

        dt[t] = 0;
        dfs2(t, 0);

        d1(s, 0); d2(t, 0);

        id = ans = inf;
        work(s, 0);
        printf("Case #%d: %d\n", cas, id);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yang_7_46/article/details/9988655


,