POJ 1985 Cow Marathon （树形DP，树的直径）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给定一棵树，然后让你找出它的直径，也就是两点中的最远距离。

析：很明显这是一个树上DP,应该有三种方式，分别是两次DFS，两次BFS，和一次DFS，我只写了后两种。

代码如下：

两次BFS:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int maxn = 1e5 + 5;

int d[maxn];

bool vis[maxn], vvis[maxn];//vis是BFS的标记，vvis是总的标记

vector<int> G[maxn], w[maxn];

//思路就是先在树上找一个点，然后从这个点开始找，找最远的点，

//然后两从最远的点找最远的点，这个所有点中的最大值就是树的直径

//d[i]表示到结点 i 的最长距离

int bfs(int root){

    memset(vis, false, sizeof(vis));

    memset(d, 0, sizeof(d));

    queue<int> q;

    q.push(root);

    int ans = root, m = 0;

    vis[root] = vvis[root] = true;

    while(!q.empty()){

        root = q.front();   q.pop();

        for(int i = 0; i < G[root].size(); ++i){

            int u = G[root][i];

            if(vis[u])  continue;

            q.push(u);

            vis[u] = vvis[u] = true;

            d[u] = d[root] + w[root][i];

            if(d[u] > m){

                ans = u;

                m = d[u];

            }

        }

    }

    return ans;

}

void init(int n){

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

        G[i].clear();

        w[i].clear();

        vvis[i] = false;

    }

}

int main(){

    int n, m, u, v, l;

    char ch;

    while(cin >> n >> m){

        init(n);

        while(m--){

            scanf("%d %d %d %c", &u, &v, &l, &ch);

            G[u].push_back(v);  w[u].push_back(l);

            G[v].push_back(u);  w[v].push_back(l);

        }

        int ans = 0;

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

            if(!vvis[i])  ans = max(ans, d[bfs(bfs(i))]);//两次BFS，第一次是找最远的点，第二次是找最远点的最远点

        cout << ans << endl;

    }

    return 0;

}

一次DFS：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int maxn = 1e5 + 5;

int f[maxn], g[maxn], ll[maxn];

vector<int> G[maxn], w[maxn];

//思路主要是找一个点的最远点加次远点就是树的直径

int dfs(int root, int fa){

    if(f[root] != -1)  return f[root];

    if(!G[root].size())  return f[root] = 0;

    int m = 0, ans = root;

    for(int i = 0; i < G[root].size(); ++i){

        int u = G[root][i];

        if(u == fa)  continue;

        if(dfs(u, root) + w[root][i] > m){

            m = f[u] + w[root][i];

            ans = u;

        }

    }

    ll[root] = ans; int  mm = 0;

    for(int i = 0; i < G[root].size(); ++i){

        int u = G[root][i];

        if(u == fa)  continue;

        if(f[u] + w[root][i] > mm && u != ll[root])

            mm = f[u] + w[root][i];

    }

    g[root] = mm;

    return f[root] = m;

}

void init(int n){

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

        G[i].clear();

        w[i].clear();

        f[i] = g[i] = ll[i] = -1;

    }

}

int main(){

    int n, m, u, v, l;

    char ch;

    while(cin >> n >> m){

        init(n);

        while(m--){

            scanf("%d %d %d %c", &u, &v, &l, &ch);

            G[u].push_back(v);  w[u].push_back(l);

            G[v].push_back(u);  w[v].push_back(l);

        }

        int ans = 0;

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

            if(f[i] == -1)  dfs(i, -1);

        for(int i = 1; i <= n; ++i)  ans = max(ans, f[i]+g[i]);

            cout << ans << endl;

    }

    return 0;

}