HDU--3721[Building Roads] 枚举+求最长路O(N^2)

题意：

给一棵树，可以移动树上的一条边，但是必须保证移动之后的图还是一棵树，问如何移动才能使得移动之后的树的直径最短。

思路：

先在原树上求直径，然后枚举直径上的边(因为要使其直径变短只可能删除直径上的某条边)。u->v.这样原树就被拆成两个子树。

(1):分别求出两个子树的直径du和dv.

(2):在每棵子树中求一点x。使这点到子树中的其他任意一点的最长距离最短。由分析可知，这一点x一定在子树的直径上，且在直径的中心两点中的其中一点（证明如下）。

(3):分别求出两棵子树的那两个关键点x后。更新答案ans_l=min(ans_l,max(du,dv,ss+ee+w)).   //ss，ee是两棵子树的关键点x到其他点的最长距离；w是当前枚举边的长度

证明如下:  摘自 http://hi.baidu.com/dispossessed/blog/item/660a8a294b9d62459922ed5f.html

假设要求的点不是直径上面的点，那么由于原图是一棵树，取这个点到直径的最短路径，交直径与一个点，这个点到其他点的最长距离一定大于交点到其他点的最长距离，这样

就说明了要求的点一定是直径上面的点，既然是直径上面的点，因为直径是一条链，显然它一定是中心附近的点。

PS.一开始的复杂度是O(N^3)，TLE，后然看了别人的题解后发现“关键点”只可能在直径的中心附近的两个点中的一个。这样就把复杂度降到了O(N^2).

CODE：

/*枚举+求最长路O(N^2)*/
/*AC代码：170ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <queue>
#define MAXN 2505
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
    int u,v,w,next;
    bool ok;
}E[3*MAXN];
int head[MAXN];
int ecnt;
int dis[MAXN],road[MAXN],pre[MAXN],cnt;
bool vis[MAXN],col[MAXN];
int N,ans_l,cas,lenc;
queue<int>Q;

void Insert(int u,int v,int w)
{
    E[ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].ok=true;
    E[ecnt].next=head[u];
    head[u]=ecnt++;
}
void Print()
{
    int i;
    for(i=1;i<=N;i++)
        printf("%d ",col[i]);
    printf("**\n");
}
void Init()
{
    int i,u,v,w;
    memset(head,-1,sizeof(head));ecnt=0;
    scanf("%d",&N);
    for(i=1;i<N;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        u++;v++;
        Insert(u,v,w);
        Insert(v,u,w);
    }
}
int BFS(int s)
{
    int i,u,v,w,res;
    while(!Q.empty()) Q.pop();
    memset(vis,false,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    memset(pre,-1,sizeof(pre));
    vis[s]=true;
    dis[s]=0;
    Q.push(s);
    while(!Q.empty())
    {
        u=Q.front();Q.pop();
        for(i=head[u];i!=-1;i=E[i].next)
        {
            if(E[i].ok==false) continue;
            v=E[i].v;w=E[i].w;
            if(!vis[v])
            {
                dis[v]=dis[u]+w;
                pre[v]=i;
                vis[v]=true;
                Q.push(v);
            }
        }
    }
	res=0;
	for(i=1;i<=N;i++)
	{
		if(dis[i]==-1) continue;
		if(dis[i]>res) res=dis[i];
	}
	return res;
}
int Go(int x,bool flag)
{
    int i,u,v,s,e,Max,l,temp[MAXN],tcnt;
    BFS(x);
    s=0;Max=0;lenc=INF;
    for(i=1;i<=N;i++)//染色
    {
        if(vis[i])
        {
            col[i]=flag;
            if(dis[i]>Max)
            {s=i;Max=dis[i];}
        }
    }
    BFS(s);
    e=0;Max=0;
    for(i=1;i<=N;i++)
    {
        if(vis[i])
        {
            if(dis[i]>Max)
            {e=i;Max=dis[i];}
        }
    }
	int sum=0;
	tcnt=0;
    u=e;
    while(true)
    {
        l=pre[u];
        if(l==-1) break;
        temp[tcnt++]=l;
		sum+=E[l].w;
        u=E[l].u;
    }
	sum/=2;
	int len=0;
	for(i=0;i<tcnt;i++)
	{
		len+=E[temp[i]].w;
		if(len>sum) break;
	}
	//最好的点就在这两个点之间
	if(tcnt==0)//避免RE
	{
		lenc=0;
		return Max;
	}
	u=E[temp[i]].u;
	v=E[temp[i]].v;
	int lu=BFS(u);
	int lv=BFS(v);
	//printf("&%d %d %d %d %d\n",tcnt,u,v,lu,lv);
	lenc=min(lu,lv);
    return Max;
}
void fuck(int ith)
{
    int i,u,v,s,e,ss,ee,ds,de,dw,Max;
    memset(col,false,sizeof(col));
    //printf("%d %d \n",road[ith],road[ith]^1);
    E[road[ith]].ok=E[road[ith]^1].ok=false;
    s=E[road[ith]].u;
    e=E[road[ith]].v;
    ds=Go(s,1); ss=lenc;
    de=Go(e,0); ee=lenc;

    //Print();

    dw=ss+ee+E[road[ith]].w;
    int res=max(dw,max(ds,de));
	
    //printf("*%d %d %d %d %d %d\n",s,e,ans_l,ds,de,dw);
    ans_l=min(ans_l,res);
    E[road[ith]].ok=E[road[ith]^1].ok=true;
}
void Run()
{
    int i,s,e,u,Max,l;
    BFS(1);
    s=1;Max=dis[1];
    for(i=2;i<=N;i++)
    {
        if(dis[i]>Max)
        {s=i;Max=dis[i];}
    }
    BFS(s);
    e=1;Max=dis[1];
    for(i=2;i<=N;i++)
    {
        if(dis[i]>Max)
        {e=i;Max=dis[i];}
    }
    ans_l=Max;
    cnt=0;
    u=e;
    while(true)
    {
        l=pre[u];
        if(l==-1) break;
        road[cnt++]=l;
        u=E[l].u;
    }
    for(i=0;i<cnt;i++)
    {
        fuck(i);
    }
}
void Solve()
{
    int i;
    Run();//求出最长路径
    printf("Case %d: %d\n",cas++,ans_l);
}
int main()
{
    int T;
    cas=1;
    scanf("%d",&T);
    while(T--)
    {
        Init();
        Solve();
    }
	return 0;
}