学步园

http://poj.org/problem?id=1985

题意：给一棵树，求树的直径

方法一）tree-DP 类似HDU2196，可以参见：

http://www.cnblogs.com/celia01/archive/2012/07/30/2615842.html

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX(a,b) ((a)>(b)?(a):(b))

struct edge
{
    int ev,w;
    edge(){}
    edge(int a,int b):ev(a),w(b){}
};
vector <edge> elist[40009];
int g[40009],f[40009],h[40009];
bool vd[40009];

void DFS1(int fv)
{
    vd[fv] = true;
    int size = elist[fv].size();
    if (!size)
    {
        f[fv] = g[fv] = 0;
        return;
    }

    int ev,w;
    for (int i = 0;i < size;i++)
    {
        ev = elist[fv][i].ev;
        w = elist[fv][i].w;
        if (vd[ev]) continue;
        DFS1(ev);
        if (f[ev] + w >= f[fv])
        {
            g[fv] = f[fv];
            f[fv] = f[ev] + w; //?
        }
        else
        {
            if (f[ev] + w > g[fv])
                g[fv] = f[ev] + w;
        }
    }
}

int main()
{
    freopen("test.txt","r",stdin);
    int N,M;
    while(~scanf("%d%d",&N,&M))
    {
        for (int i = 1;i <= N;i++)
            elist[i].clear();
        int fv,ev,w;
        char dir[10];
        for (int i = 1;i <= M;i++)
        {
            scanf("%d%d%d%s",&fv,&ev,&w,dir);
            elist[fv].push_back(edge(ev,w));
            elist[ev].push_back(edge(fv,w));
        }

        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        memset(vd,0,sizeof(vd));
        DFS1(1);

        int maxx = 0;
        for (int i = 1;i <= N;i++)
        {
            //cout<<"i = "<<i<<" "<<f[i]<<" "<<g[i]<<endl;
            if (f[i] + g[i] > maxx) maxx = f[i] + g[i];
        }
        printf("%d\n",maxx);
    }

    return 0;
}
/*
这道题目给HDU2196有点不一样，那道题目给出来的数据就已经是建好的树；
而这题给出的数据不是树，要自己建。。。。。
*/

方法二）两遍BFS/DFS

本来是做DP看到这道题的，但这道题正统的做法却是BFS，所以就也顺带写了个

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX(a,b) ((a)>(b)?(a):(b))

struct edge
{
    int ev,w;
    edge(){}
    edge(int a,int b):ev(a),w(b){}
};
vector <edge> elist[40009];
bool vd[40009];
int s,t;
int maxx;

void DFS(int fv,int dis)
{
    vd[fv] = true;
    int size = elist[fv].size();

    int ev,w;
    for (int i = 0;i < size;i++)
    {
        ev = elist[fv][i].ev;
        w = elist[fv][i].w;
        if (vd[ev]) continue;
        DFS(ev,dis + w);
    }
    if (dis > maxx)
    {
        maxx = dis;
        s = fv;
    }
}

int main()
{
    freopen("test.txt","r",stdin);
    int N,M;
    while(~scanf("%d%d",&N,&M))
    {
        for (int i = 1;i <= N;i++)
            elist[i].clear();
        int fv,ev,w;
        char dir[10];
        for (int i = 1;i <= M;i++)
        {
            scanf("%d%d%d%s",&fv,&ev,&w,dir);
            elist[fv].push_back(edge(ev,w));
            elist[ev].push_back(edge(fv,w));
        }

        memset(vd,0,sizeof(vd));
        s = t = maxx = 0;
        DFS(1,0);
        
        memset(vd,0,sizeof(vd));
        maxx = 0;
        DFS(s,0);

        printf("%d\n",maxx);
    }

    return 0;
}