bzoj4890 [TJOI2017]城市

​​http://www.elijahqi.win/archives/3133​​​

题目描述

从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有ri座城市，《-1条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路(即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？

输入输出格式

输入格式：

输入数据的第一行为一个整数n,代表城市个数。

接下来的n - 1行分别代表了最初的n-1条公路情况。每一行都有三个整数u,v,d。u,v代表这条公路的两端城市标号，d代表这条公路的交通费用。

1 <= u,v <= n,1<= d <= 2000

输出格式：

输出数据仅有一行，一个整数，表示进行了最优的改造之后，该地区两城市 之间最大交通费用。

输入输出样例

输入样例#1： 复制

5

1 2 1

2 3 2

3 4 3

4 5 4

输出样例#1： 复制

7

s

3s n=5000 n^2暴力可以过

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=5500;
const int inf=0x3f3f3f3f;
struct node{
    int x,y,z,next;
}data[N<<1];
int h[N],num=1,id[N],ans=inf,ed,st,dis1[N],ans1,n;bool tag[N<<1];
inline int dfs1(int x,int fa){
    int mx1=0,mx2=0,mx1id=0,mx2id=0,tmp=0;
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y;if (tag[i]||y==fa) continue;
        tmp=dfs1(y,x);tmp+=data[i].z;
        if (tmp>mx1) mx2=mx1,mx2id=mx1id,mx1=tmp,mx1id=y;else if(tmp>mx2) mx2=tmp,mx2id=y;
    }if (mx1+mx2>ans1) {ans1=mx1+mx2;st=id[mx1id];ed=id[mx2id];if (!mx2id) ed=x;}
    if (mx1id) id[x]=id[mx1id];return mx1;
}
inline bool dfs2(int x,int fa,int dis){
    if (x==ed) {dis1[x]=0;if (x==st) ans1=0;return 1;}
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y,z=data[i].z;if (tag[i]||y==fa) continue;
        if (dfs2(y,x,z+dis)){ans1=min(ans1,max(dis,dis1[y]+z));dis1[x]=dis1[y]+z;return 1;}
    }return 0;
}
int main(){
    freopen("bzoj4890.in","r",stdin);
    n=read();
    for (int i=1;i<n;++i){static int x,y,z;
        x=read();y=read();z=read();
        data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z;data[num].x=x;
        data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=z;data[num].x=y;
    }for (int i=2;i<=num;i+=2){static int x,y,dia1,dia2,r1,r2;
        tag[i]=tag[i^1]=1;x=data[i].x;y=data[i].y;
        for (int i=1;i<=n;++i) id[i]=i;
        dfs1(x,x);dia1=ans1;ans1=inf;dfs2(st,st,0);r1=ans1;ans1=0;
        dfs1(y,y);dia2=ans1;ans1=inf;dfs2(st,st,0);r2=ans1;ans1=0;
        ans=min(ans,max(dia1,max(dia2,r1+r2+data[i].z)));tag[i]=tag[i^1]=0;
    }printf("%d\n",ans);
    return 0;
}