本文共 1462 字，大约阅读时间需要 4 分钟。

对于一张图上的任意三个点A,B,C 求max(min(dis[A][C],dis[B][C])+dis[A][B])

我们先确定A，B为树上直径，可以用反证法简单证一下

然后就可以对于A和B两个点算一下其他点到A/B的距离，然后枚举点C即可

代码

#include
   
    using namespace std;const int maxn=200000+5;int n,m,tot,st,ed;int head[maxn];long long dis1[maxn],dis2[maxn];struct edge{	int to,nxt;	long long v;}e[maxn<<1];void add(int x,int y,long long z){	e[++tot].nxt=head[x];	head[x]=tot;	e[tot].to=y;	e[tot].v=z;}void dfs1(int x,int fa){	for(int i=head[x];i;i=e[i].nxt)	{		int to=e[i].to;		int v=e[i].v;		if(to==fa) continue;		dis1[to]=dis1[x]+v;		if(dis1[to]>dis1[st]) st=to;		dfs1(to,x);	}}void dfs2(int x,int fa){	for(int i=head[x];i;i=e[i].nxt)	{		int to=e[i].to;		int v=e[i].v;		if(to==fa) continue;		dis2[to]=dis2[x]+v;		if(dis2[to]>dis2[ed]) ed=to;		dfs2(to,x);	}}void dfss1(int x,int fa){	for(int i=head[x];i;i=e[i].nxt)	{		int to=e[i].to;		int v=e[i].v;		if(to==fa) continue;		dis1[to]=dis1[x]+v;		dfss1(to,x);	}}void dfss2(int x,int fa){	for(int i=head[x];i;i=e[i].nxt)	{		int to=e[i].to;		int v=e[i].v;		if(to==fa) continue;		dis2[to]=dis2[x]+v;		dfss2(to,x);	}}int main(){	scanf("%d%d",&n,&m);	int x,y;	long long z;	for(int i=1;i<=m;i++)	{		scanf("%d%d%lld",&x,&y,&z);		add(x,y,z); add(y,x,z);	}	dfs1(1,0);	dfs2(st,0);	long long tmp=dis2[ed];	memset(dis1,0,sizeof(dis1));	memset(dis2,0,sizeof(dis2));	dfss1(st,0);	dfss2(ed,0);	long long ans=0;	for(int i=1;i<=n;i++)	{		if(i==st || i==ed) continue;		ans=max(ans,min(dis1[i],dis2[i]));	}	printf("%lld",ans+tmp);	return 0;}
   

转载地址：http://xcwm.baihongyu.com/