傳送門

80分

$ Floyd $ 樹的直徑可以通過枚舉求出。直徑的兩個端點$ maxi,maxj $ ，由此可知對于一個點 $ k $ ，如果滿足 $ d[maxi][k]+d[k][maxj]==d[maxi][maxj] $ 那么 $ k $ 點一定在直徑上。分別枚舉位于直徑上的起點 $ s $ 與終點 $ t $ 。 $ ecg $ 定義為 $ max{d(v,F)} $ 那么枚舉出的線段的 $ ecg $ 一定為：
$ max{min{d[maxi][s],d[maxi][t]},min{d[maxj][s],d[maxj][t]}} $

因為 $ maxi $ 與 $ maxj $ 到線段的距離的最大值 一定是最大的否則 $ maxi-maxj $ 就不是直徑。

比較得最小 $ ecg $ 即可。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std ; #define re register const int maxn = 1005 ;inline int read () {int f = 1 , x = 0 ;char ch = getchar () ;while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar () ;}while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;}return x * f ; }int n , s , x , y , z ; int dis[305][305] , ans = 1e9 ;int main () {n = read () ; s = read () ;for(re int i = 1 ; i <= n ; ++ i)for(re int j = 1 ; j <= n ; ++ j)if(i != j) dis[i][j] = dis[j][i] = 1e9 ; for(re int i = 1 ; i < n ; ++ i) {x = read () ; y = read () ; z = read () ;dis[x][y] = dis[y][x] = z ;}for(re int k = 1 ; k <= n ; ++ k)for(re int i = 1 ; i <= n ; ++ i)for(re int j = 1 ; j <= n ; ++ j) {if(dis[i][j] > dis[i][k] + dis[k][j])dis[i][j] = dis[i][k] + dis[k][j] ; }int maxx = 0 , maxi , maxj ;for(re int i = 1 ; i <= n ; ++ i)for(re int j = 1 ; j <= n ; ++ j) if(dis[i][j] < 1e9 && dis[i][j] > maxx) {maxx = dis[i][j] ;maxi = i ;maxj = j ;}for(re int i = 1 ; i <= n ; ++ i) if(dis[maxi][i] + dis[maxj][i] == dis[maxi][maxj]) {for(re int j = 1 ; j <= n ; ++ j) if(dis[maxi][j] + dis[maxj][j] == dis[maxi][maxj]) {if(dis[i][j] > s) continue ;int ecg ;ecg = max(min(dis[i][maxi] , dis[j][maxi]) , min(dis[maxj][i] , dis[maxj][j])) ;ans = min(ans , ecg) ;}}printf("%d\n" , ans) ;return 0 ; }

轉載于:https://www.cnblogs.com/Stephen-F/p/10665656.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的洛谷P1099 树网的核的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。