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;
}