2015年3月24日 星期二

2015/03/24 HSNU OJ Problem : 288 - Dreaming

/*
    從樹上任一點x 開始DFS
    找到距離x 最遠的點y

    再從y做一次DFS
    找到離y 最遠的點z
    則(y,z) 為此樹上
    相距最遠的點對之一
    此path為 樹半徑之一
    
    必有一個樹中心
    在樹半徑上
*/
// http://hoj.twbbs.org/judge/problem/view/288
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef pair<int, int> TC;
#define t first
#define c second

vector<TC> v[200000];
bool visit[200000];
int fa[200000];
int dis[200000];
vector<int> pass;

vector<int> dep;

int N, M, L;
int Ans = 0;

void DFS(int O)
{
    visit[O] = true;
    pass.push_back(O);

    for(int vi = 0; vi < v[O].size(); vi++)
    {
        int t = v[O][vi].t;
        int c = v[O][vi].c;

        if( !visit[t] )
        {
            fa[t] = O;
            dis[t] = dis[O]+c;
            DFS(t);
        }
    }
}

int main()
{
    scanf("%d %d %d", &N, &M, &L);

    for(int Mi = 0; Mi < M; Mi++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        v[a].push_back(TC(b, c) );
        v[b].push_back(TC(a, c) );
    }

    fill(visit, visit+N, false);

    for(int Ni = 0; Ni < N; Ni++)
        if( !visit[Ni] )
        {
            pass.clear();
            fa[Ni] = Ni;
            dis[Ni] = 0;
            DFS(Ni);

            int t;

            t = Ni;

            for(int pi = 0; pi < pass.size(); pi++)
            {
                int q = pass[pi];
                visit[q] = false;

                if( dis[q] > dis[t] ) t = q;
            }

            pass.clear();
            fa[t] = t;
            dis[t] = 0;
            DFS(t);

            t = Ni;

            for(int pi = 0; pi < pass.size(); pi++)
            {
                int q = pass[pi];
                if( dis[q] > dis[t] ) t = q;
            }

            int lth = dis[t];
            Ans = max(Ans, lth);

            while(1)
            {
                int q = fa[t];

                if( max(dis[t], lth-dis[t]) <= max(dis[q], lth-dis[q]) ) break;
                t = fa[t];
            }

            dep.push_back(max(dis[t], lth-dis[t]) );
        }

    sort(dep.begin(), dep.end(), greater<int>());

    for(int di = 1; di < dep.size(); di++)
        dep[di] += L;

    sort(dep.begin(), dep.end(), greater<int>());

    if( dep.size() >= 2 )
        Ans = max(Ans, dep[0]+dep[1]);

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

沒有留言:

張貼留言