P1099 [NOIP2007 提高组] 树网的核

#include<bits/stdc++.h>
using namespace std;
#define edge(i,x) for(int i=h[x]; i; i=nt[i])
#define For(i,x,y) for(int i=x; i<=y; i++)
const int N=1e3;
int n,s,h[N],nt[N*2],to[N*2],w[N*2],cnt;
void add(int x,int y,int z)
{
    nt[++cnt]=h[x]; h[x]=cnt; to[cnt]=y; w[cnt]=z;
}
int p[N],nxt[N];
int d[N],st,maxn,ed;
void dfs1(int x,int fa)
{
    edge(i,x)
    {
        int y=to[i];
        if(y==fa)continue;
        //cout<<x<<" "<<y<<" ";
        d[y]=d[x]+w[i];
       // cout<<d[y]<<endl;
        if(d[y]>maxn)
        {
            maxn=d[y],st=y;
        }
        dfs1(y,x);
    }
}
int w1[N],w2[N];
void dfs2(int x,int fa)
{
    edge(i,x)
    {
        int y=to[i];
        if(y==fa)continue;
        d[y]=d[x]+w[i];
        if(d[y]>maxn)
        {
            maxn=d[y],ed=y;
        }
        p[y]=x;
        dfs2(y,x);
    }
}
void dfs3(int x,int fa)
{
    d[x]=0;
    edge(i,x)
    {
        int y=to[i];
        if(y==fa||y==nxt[x]||y==p[x])continue;
        dfs3(y,x);
        d[x]=max(d[x],d[y]+w[i]);
    }
}
int ans;
int main()
{
    //freopen("text.in","r",stdin);
    cin>>n>>s;
    For(i,1,n-1){
        int A,B,C;
        cin>>A>>B>>C;
        add(A,B,C);
        add(B,A,C);
    }
    st=0,maxn=-1;
    dfs1(1,0);
    //cout<<maxn<<endl;
    maxn=-1;
    memset(d,0,sizeof(d));
    dfs2(st,0);
    //cout<<st<<" "<<ed<<endl;
    int j=ed;
    //for(int i=ed; i; i=p[i])
    //{
    //    cout<<i<<" ";
    //}
    //cout<<endl;
    for(int i=ed; i; i=p[i])
        nxt[p[i]]=i;
    ans=(1<<30);
    //for(int i=ed; i; i=p[i])cout<<d[i]<<" ";
    //cout<<endl;
    for(int i=ed; i; i=p[i])
    {
        while(p[j]&&d[i]-d[p[j]]<=s)j=p[j];
        ans=min(ans,max(d[ed]-d[i],d[j]));
    }
    //cout<<ans<<endl;
    for(int i=ed; i; i=p[i])
        dfs3(i,0),ans=max(ans,d[i]);//,printf("%d ",d[i]);
    //cout<<endl;
    cout<<ans<<endl;
}

原文地址：http://www.cnblogs.com/dadidididi/p/16800359.html