欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj Cow Marathon树的直径

程序员文章站 2022-07-04 20:07:07
...

poj Cow Marathon树的直径

。。。。。。

在时间超限的边缘挣扎;

两次dfs,因为第一次找到最远的出口,但是前面还有没有搜的;

然后从这次出口进行dfs;

#pragma GCC optimize(2)

#include <iostream>

#include <cstring>

#include <vector>

#define maxn 1000005

typedef long long ll;

using namespace std;

ll n,m,ma,fl;

ll flag[maxn];

vector < pair <ll,ll> > plan[maxn];

void bulid(ll a,ll b,ll c)
{
    plan[a].push_back(make_pair(b,c));
    plan[b].push_back(make_pair(a,c));
}

void dfs1(ll be,ll step)
{
    if(flag[be] == 0)
    {
        flag[be] = 1;
    }
    else
    {
        return ;
    }
    if(step > ma)
    {
        ma = step;
        fl = be;
    }
    for(int i = 0; i < plan[be].size(); i ++)
    {
        dfs1(plan[be][i].first,step+plan[be][i].second);
    }
}

void dfs2(ll be,ll step)
{
    if(flag[be] == 0)
    {
        flag[be] = 1;
    }
    else
    {
        return ;
    }
     ma = max(ma,step);
    for(int i = 0; i < plan[be].size(); i ++)
    {
        dfs2(plan[be][i].first,step+plan[be][i].second);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;

    while(m--)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        char z;
        cin >> z;
        bulid(a,b,c);
    }

    dfs1(1,0);
    memset(flag,0,sizeof(flag));
    ma = 0;
    dfs2(fl,0);
    cout << ma << endl;

    return 0;
}