自动搬运

查看原文

来自洛谷，原作者为

	Y25t 我从来没觉得打算法竞赛开心过。

搬运于2025-08-24 22:15:22，当前版本为作者最后更新于2020-01-03 13:56:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我居然切了一道IOI题！

由于题目要使最长路径最短，于是很容易想到贪心策略：

每棵树和其它树连边的点一定是这棵树上能走到的最远距离最短的的点（由于本人语文水平太菜，这句话有点绕 qwq )

如果我们把上述的最短距离称作半径 $r$，$1,2,3...$ 是树按照 $r$ 排序后的。那么最后链接成的树应该长这样：

那么最后的答案只有三种情况：

1、原树的最长直径

2、$r_1+r_2+l$

3、$r_2+r_3+l*2$

求个 $max$ 就好了~~~

至于树的半径和直径怎么求。注意到树上离某个点最远的点一定是树的直径的某个端点，于是就可以 $O(n)$ dfs求出。

/*

注意每次dfs前清空数组不能用memset，不然效率会被卡到 $O(n^2)$

我就因为这个T了好久，以为是常数问题，于是代码中加了很多无用的卡常操作，导致它跑的特别快。。。

*/

以下代码：

#include<cstdio>
#include<algorithm>
#define Int register int
#define N 100005

inline void rd(int &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
}

int n,m,l;

int hd[N],_hd;
struct edge{
	int v,w,nxt;
}e[N<<1];
inline void addedge(int u,int v,int w){
	e[++_hd]=(edge){v,w,hd[u]};
	hd[u]=_hd;
}

bool flg;//为了卡常 
int q[N],_q;

int dis[2][N];
bool vis[N];
inline void dfs(Int u,Int fa,Int opt){
	if(!flg)
		q[++_q]=u;
	vis[u]=1;
	for(Int i=hd[u];i;i=e[i].nxt){
		Int v=e[i].v,w=e[i].w;
		if(v==fa)
			continue;
		dis[opt][v]=dis[opt][u]+w;
		dfs(v,u,opt);
	}
}

inline int fnd(Int u){
	for(Int i=1;i<=_q;i++){
		Int v=q[i];
		dis[0][q[i]]=0;
	}//这里千万不能用memset 
	dfs(u,0,0);
	flg=1;
	Int res=u;
	for(Int i=1;i<=_q;i++){
		Int v=q[i];
		if(dis[0][v]>dis[0][res])
			res=v;
	}
	return res;
}

int r1,r2,r3,ans,cnt;//r1、r2、r3为前三大的半径，ans一开始为最长直径（第一种情况），cnt表示原来有几棵树 
inline void sol(Int u){
	cnt++;
	flg=_q=0;
	dfs(fnd(fnd(u)),0,1);//最里面的fnd返回的是直径的一个端点，第二个fnd更新dis[0]，返回另一个端点，dfs更新dis[1] 
	Int r=1e9;
	for(Int i=1;i<=_q;i++){
		Int v=q[i],disv=std::max(dis[0][v],dis[1][v]);
		r=std::min(r,disv);//更新当前树的半径 
		ans=std::max(ans,disv);//更新最大直径 
	}
	if(r>r1){
		r3=r2;
		r2=r1;
		r1=r;
	}
	else if(r>r2){
		r3=r2;
		r2=r;
	}
	else if(r>r3)
		r3=r;
}

int main(){
	rd(n),rd(m),rd(l);
	for(Int i=1;i<=m;i++){
		Int u,v,w;
		rd(u),rd(v),rd(w);
		addedge(++u,++v,w);
		addedge(v,u,w);
	}
	for(Int i=1;i<=n;i++)
		if(!vis[i])
			sol(i);
	if(cnt>1)
		ans=std::max(ans,r1+r2+l);//第二种情况 
	if(cnt>2)
		ans=std::max(ans,r2+r3+(l<<1));//第三种情况 
	printf("%d\n",ans);

    #define w 0
    return ~~('0')?(0^w^0):(0*w*0);
}