树形dp - 求树的直径

随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
　　现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？

　　其中，可以兴建的路线均是双向的，他们之间的长度均大于0。

Input　　测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；

　　接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。

　　
[Technical Specification]

　　1. n<=100000

　　2. m <= 1000000

　　3. 1<= u, v <= n

　　4. w <= 1000

Output　　对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。

Sample Input

Sample Output

YES

题意 ： 先判断一下图中是否有环，有就直接输出YES，否则在输出这个无环图中的最长链
思路分析：判断一个图中是否有环，采用并查集即可，找树上的最长链，也就是树的直径，有两种方法，一种是用采用树形dp,那么树上最长的链就是当前结点最远和次远的儿子加起来的和。
　　　dp[x][0] 表示树上次远的距离是多少， dp[x][1]表示树上最远的距离是多少。
代码示例：

const int maxn = 1e5+5;

int n, m;

struct node

{

    int to, cost;

    node(int _to=0, int _cost=0):to(_to), cost(_cost){}

};

vector<node>ve[maxn];

int f[maxn];

int fid(int x){

    if (x != f[x]) f[x] = fid(f[x]);

    return f[x];

}

bool pt[maxn];

int dp[maxn][2];

int ans;

void dfs(int x, int fa){

    pt[x] = true;

    for(int i = 0; i < ve[x].size(); i++){

        int to = ve[x][i].to;

        int cost = ve[x][i].cost;

        if (to == fa) continue;

        dfs(to, x);

        if (dp[x][1] < dp[to][1]+cost){

            dp[x][0] = dp[x][1];

            dp[x][1] = dp[to][1]+cost;

        }

        else if (dp[x][0] < dp[to][1]+cost){

            dp[x][0] = dp[to][1]+cost;

        }

    }

    ans = max(ans, dp[x][1]+dp[x][0]);

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    int x, y, z;

    while(~scanf("%d%d", &n, &m)){

        for(int i = 1; i <= n; i++) f[i]=i, ve[i].clear();

        int flag = 0;

        for(int i = 1; i <= m; i++){

            scanf("%d%d%d", &x, &y, &z);

            ve[x].push_back(node(y, z));

            ve[y].push_back(node(x, z));

            int x1 = fid(x), x2 = fid(y);

            if (x1 == x2) flag = 1;

            else f[x1] = x2;

        }

        if (flag) {printf("YES\n"); continue;}

        memset(pt, false, sizeof(pt));

        memset(dp, 0, sizeof(dp));

        ans = 0;

        for(int i = 1; i <= n; i++){

            if (!pt[i]) dfs(i, 0);

        }

        printf("%d\n", ans);

    }

    return 0;

}

秒客网

树形dp - 求树的直径

相关文章