1850：【07NOIP提高组】树网的核

传送门

题干分析

这是一道图论的题（没学过?别怕），分析可知 分析了两个小时 我们要求在找到小于s长的线段，并且满足到该线段最远的点最小。

具体思路

用二维数组存下点与点之间的联系，然后用 floyed 求出每两点之间的最短长度（没学过？啃书去），随后我们只需枚举线段，找到最小值即可。点与线段间距离公式： $$(f[k][i]+f[k][j]-f[i][j])/2$$

ps. f 数组是floyed求出的两点间最短距离

证明该公式如下： 1.如图，当 k在线段ij两侧时 （这里只有在右边，但是左右证明方法相同） $$f[k][i]=f[i][j]+f[j][k]$$ $$f[k][j]=f[k][j]$$ $$f[i][j]=f[i][j]$$所以 $$(f[k][i]+f[k][j]-f[i][j])/2$$等于 $$(f[i][j]+f[j][k]+f[k][j]-f[i][j])/2$$即 $$(f[j][k]+f[j][k])/2$$所以在此时 $$(f[k][i]+f[k][j]-f[i][j])/2=f[j][k]$$由图可知 f[j][k] 即为k到线段ij的距离 如图，当点k到线段ij的最短路径在ij中部时

$$f[k][i]=f[i][m]+f[m][k]$$ $$f[k][j]=f[j][m]+f[m][k]$$ $$f[i][j]=f[i][j]$$

所以 $$(f[k][i]+f[k][j]-f[i][j])/2$$等于 $$(f[i][m]+f[m][k]+f[j][m]+f[m][k]-f[i][j])/2$$即 $$(f[m][k]+f[m][k])/2$$所以在此时 $$(f[i][m]+f[m][k]+f[j][m]+f[m][k]-f[i][j])/2=f[m][k]$$由图可知 f[m][k] 即为k到线段ij的距离至此，公式正确性证明完毕

代码(够短吧)

#include<bits/stdc++.h> using namespace std; int n,m,f[301][301],ans,sum,x,y,z; int main(){ while(cin>>n>>m){ memset(f,63,sizeof(f)); for(int i=1;i<n;i++){ scanf("%d %d %d",&x,&y,&z); f[x][y]=f[y][x]=z; } for(int i=1;i<=n;i++) f[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); ans=INT_MAX; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) if(f[i][j]<=m){ sum=0; for(int k=1;k<=n;k++) sum=max(sum,(f[k][i]+f[k][j]-f[i][j])/2); ans=min(ans,sum); } printf("%d\n",ans); } return 0; }