[TJOI2017]城市

洛咕

分析:\(n=5000,3s?\)可以直接\(n^2\)过.枚举删哪条边,这条边的两端分别是一个联通块,求每个联通块以哪个点为根时可以使得联通块内到根距离最大的点距离最小,这个点其实就是连通块的直径的中点,可以用\(dfs\)\(O(n)\)求出直径后,暴力枚举直径上的点找到中点.

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=5005;
int n,maxx,pos,ans=1<<30,dis[N],pre[N];
struct edge{int x,y,z,num;}a[N];
int tot,head[N],nxt[N<<1],to[N<<1],w[N<<1];
inline void add(int a,int b,int c){
	nxt[++tot]=head[a];head[a]=tot;to[tot]=b;w[tot]=c;
}
inline void dfs(int u,int fa,int rt){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa||v==rt)continue;
		dis[v]=dis[u]+w[i];pre[v]=u;
		if(dis[v]>maxx)maxx=dis[v],pos=v;
		dfs(v,u,rt);
	}
}
int main(){
	n=read();
	for(int i=1;ians)continue;
		int en2=maxx,pos2=pos;
		int now=0,mid=en2/2;
		while(pos2!=pos1){
			if(abs(mid-now)>abs(mid-now-(dis[pos2]-dis[pre[pos2]])))now+=dis[pos2]-dis[pre[pos2]],pos2=pre[pos2];
			else break;
		}
		int hehe1=pos2,hehe2=max(now,en2-now);		
		maxx=0;dis[a[i].y]=0;
		dfs(a[i].y,a[i].x,a[i].x);
		maxx=0;dis[pos]=0;pos1=pos;
		dfs(pos,0,a[i].x);pre[pos1]=0;
		if(maxx>ans)continue;
		int en4=maxx;pos2=pos;
		now=0;mid=en4/2;
		while(pos2!=pos1){
			if(abs(mid-now)>abs(mid-now-(dis[pos2]-dis[pre[pos2]])))now+=dis[pos2]-dis[pre[pos2]],pos2=pre[pos2];
			else break;
		}
		int hehe3=pos2,hehe4=max(now,en4-now);
		ans=min(ans,max(hehe2+hehe4+a[i].z,max(en2,en4)));
	}
	printf("%d\n",ans);
    return 0;
}

动态规划-树形DP

[TJOI2017]城市

洛咕

相关

标签