做个网站页面多钱,北京定制公交网站,网站自动推广,唐山网站制作专业传送门 80分 $ Floyd $ 树的直径可以通过枚举求出。直径的两个端点$ maxi,maxj $ #xff0c;由此可知对于一个点 $ k $ #xff0c;如果满足 $ d[maxi][k]d[k][maxj]d[maxi][maxj] $ 那么 $ k $ 点一定在直径上。分别枚举位于直径上的起点 $ s $ 与终点 $ t $ 。 $ ecg $ 定…传送门 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
