bzoj 3246: [Ioi2013]Dreaming

.

题意：给出一个森林，要把它们连成一棵树，新连的边的边权为L，问最远的两个点间的距离最短是多少。
题解：答案首先至少是每棵树的直径的最大值。考虑连起来的状况，最优肯定是每棵树直径的中点连起来（即从这个点到其他点的最远距离最短）。答案就是max(m1+l+m2,m2+l*2+m3)，其中m1,m2,m3分别是最长、次长、次次长的深度。
代码：

#include<bits/stdc++.h>
#define pa pair<long long,long long>
using namespace std;
int n,m,num=0,fst[500010],pre[500010],ttf[500010],now=0;
long long dis[500010],l,ans=0,m1=0,m2=0,m3=0;
bool tf[500010];
struct edge
{
    int x,y,n;
    long long c;
}e[1000010];
void ins(int x,int y,long long c)
{
    e[++num]={x,y,fst[x],c};
    fst[x]=num;
}
int bfs(int x)
{
    // memset(dis,63,sizeof(dis));
    static queue<int>q;
    now++;
    q.push(x);
    dis[x]=0;
    pre[x]=0;
    int ans=-1;
    while(!q.empty())
    {
        int x=q.front();
        tf[x]=1;
        ttf[x]=now;
        if(ans==-1||dis[ans]<dis[x])
        ans=x;
        // printf("%d %d %d %d\n",x,dis[x],ans,dis[ans]);
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(ttf[y]!=now)
            {
                dis[y]=dis[x]+e[i].c;
                pre[y]=i;
                q.push(y);
            }
        }
        q.pop();
    }
    // puts("");
    return ans;
}
pa wk(int x)
{
    int hh=bfs(bfs(x));/*
    for(int i=0;i<n;i++)
    printf("%d ",dis[i]);
    puts("");*/
    long long oo=0;
    for(int i=pre[hh];i;i=pre[e[i].x])
    {
        oo+=e[i].c;
        if(oo>(dis[hh]>>1))
        {
            return make_pair(dis[hh],min(oo,dis[hh]-oo+e[i].c));
        }
    }
    return make_pair(0LL,0LL);
}
int main()
{
    scanf("%d%d%lld",&n,&m,&l);
    for(int i=0;i<m;i++)
    {
        int x,y;
        long long c;
        scanf("%d%d%lld",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    int r=0;
    for(int i=0;i<n;i++)
    {
        if(!tf[i])
        {
            r++;
            pa hh=wk(i);
            // printf("%d %d %d\n\n",i,hh.first,hh.second);
            if(hh.second>=m1)
            {
                m3=m2;
                m2=m1;
                m1=hh.second;
            }
            else if(hh.second>=m2)
            {
                m3=m2;
                m2=hh.second;
            }
            else if(hh.second>=m3)
            {
                m3=hh.second;
            }
            ans=max(ans,hh.first);
        }
    }
    // printf("%d %lld %lld %lld\n",r,m1,m2,m3);
    if(r>=2)
    ans=max(ans,m1+m2+l);
    if(r>=3)
    ans=max(ans,m2+m3+l*2);
    printf("%lld",ans);
}