BZOJ3246 IOI2013Dreaming

　　如果将森林里每棵树都各自看做一个点，那么最后所连成的树应该是一颗菊花，否则将叶子节点父亲改为根不会更劣。

　　对于每个点所代表的树，其和根节点相连的点应该是到其他点距离最大值最小的点。这个点显然是直径的中点。而距离最大值就可以作为点的权值了。

　　显然根节点应该是权值最大的。这样连完后讨论一下答案即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 500010

#define inf 1000000000

int n,m,l,p[N],deep[N],fa[N],value[N],cnt=,t=,ans;

bool flag[N];

struct data{int to,nxt,len;

}edge[N<<];

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

int dfs1(int k)

{

    int mx=k;flag[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (!flag[edge[i].to])

    {

        deep[edge[i].to]=deep[k]+edge[i].len;

        int x=dfs1(edge[i].to);

        if (deep[x]>deep[mx]) mx=x;

    }

    return mx;

}

int dfs2(int k)

{

    int mx=k;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k])

    {

        fa[edge[i].to]=k;

        deep[edge[i].to]=deep[k]+edge[i].len;

        int x=dfs2(edge[i].to);

        if (deep[x]>deep[mx]) mx=x;

    }

    return mx;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3246.in","r",stdin);

    freopen("bzoj3246.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),l=read();

    for (int i=;i<=m;i++)

    {

        int x=read()+,y=read()+,z=read();

        addedge(x,y,z),addedge(y,x,z);

    }

    for (int i=;i<=n;i++)

    if (!flag[i])

    {

        deep[i]=;int root=dfs1(i);

        deep[root]=;int x=dfs2(root);

        value[++cnt]=inf;ans=max(ans,deep[x]);

        for (int y=x;y;y=fa[y])

        value[cnt]=min(value[cnt],max(deep[x]-deep[y],deep[y]));

    }

    sort(value+,value+cnt+);reverse(value+,value+cnt+);value[cnt+]=value[cnt+]=-inf;

    cout<<max(ans,max(value[]+value[]+l,value[]+value[]+(l<<)));

    return ;

}