poj 1985 Cow Marathon 【树的直径】

向右看齐 2022-08-13 04:28 136阅读 0赞

题目：[poj 1985 Cow Marathon][]

题意：给出一个树，让你求树的直径。

分析：

树的直径：树上两点之间的最大距离。

我们从任意一点出发，BFS一个最远距离，然后从这个点出发，在BFS一个最远距离，就是树的直径、

AC代码：

/*
    POJ:1985 Cow Marathon
    2014/10/12/21:18
    Yougth*/
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int N = 44000;
    struct Node
    {
        int to,cap;
    };
    vector<Node> v[N];
    int vis[N],dis[N];
    int ans;
    int BFS(int x)
    {
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(x);
        vis[x]=1;
        int point = 0;
        while(!q.empty())
        {
            int f=q.front();
            q.pop();
            if(dis[f]>ans)
            {
                ans = dis[f];
                point = f;
            }
            for(int i=0;i<v[f].size();i++)
            {
                Node tmp = v[f][i];
                if(vis[tmp.to]==0)
                {
                    vis[tmp.to]=1;
                    dis[tmp.to] = dis[f] + tmp.cap;
                    q.push(tmp.to);
                }
            }
        }
        return point;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<m;i++)
            {
                int x,y,z;
                char c;
                scanf("%d %d %d %c",&x,&y,&z,&c);
                v[x].push_back((Node){y,z});
                v[y].push_back((Node){x,z});
            }
            ans = 0;
            int point = BFS(1);
            ans = 0;
            BFS(point);
            printf("%d\n",ans);
            for(int i=0;i<=n;i++)
                v[i].clear();
        }
        return 0;
    }

[poj 1985 Cow Marathon]: http://poj.org/problem?id=1985