真心地,这一道题我照着题解抄都抄错了
然后我就WA的一声哭了出来
我是想练习树的直径结果实在是找不到题目了于是就用这玩意来练手…
结果… 我好像是在debug的时候吧题解直接复制了一遍…
题目描述
某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。
输入输出格式
输入格式：
输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出格式：
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
输入输出样例
输入样例#1：
5 2
1 2 5
2 3 2
2 4 4
2 5 3
输出样例#1：
5
输入样例#2：
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
输出样例#2：
5
说明
【数据规模和约定】
对于20%的数据，n<=300。
对于50%的数据，n<=3000。
对于100%的数据，n<=300000，边长小等于1000。
code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define maxn 710000
using namespace std ;
int read() ;
int n , m , s;
struct tree{
int x , y , z , next ;
}a[maxn] ;
int t ;int cnt ;
int head[maxn] , vis[maxn] , dis[maxn] ;
void add (int x , int y , int z) ;
int root , l , r , ans = 99999999 , sum ;
int f[maxn][40] , dep[maxn] ;
int lca(int x , int y) ;int tot ;
void init() ;
void dfs1(int u,int fa) ;
void dfs2(int u,int fa) ;
int main() {
n=read();s=read();
for(int i=1;i<n;i++)
{
int x , y , z ;
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
dfs1(1,0);
for(int i=1;i<=n;i++)
{
if(!root||dis[i]>dis[root]) root=i;
}
memset(dis,0,sizeof(dis));
dep[root]=1;dfs2(root,0);
for(int i=1;i<=n;i++)
{
if(!t||dis[i]>dis[t]) t=i;
}
init();
l=t;r=t;vis[t]=1;
// n = read() , s = read() ;
// for(int i = 1 ; i <= n-1 ; i ++) {
// int x , y , z ;
// x = read() , y = read(), z = read() ;
// add(x,y,z) ;
// add(y,x,z) ;
// }
// dfs1(1,0) ;
// for(int i = 1 ; i <= 0 ; i ++) {
// if(!root||dis[i] > dis[root]) root = i ;
// }
// memset(dis,0,sizeof(dis)) ;
// dep[root] = 1 ;
// dfs2(root,0) ;
// for(int i = 1 ; i <= n ; i ++) {
// if(!tot||dis[i] > dis[tot]) tot = i ;
// }
// init () ;
// int l , r ;
// l = tot , r = tot ; vis[tot] = 1 ;
// while(l != 0) {
// sum = 0 ;
// if(dis[r] - dis[l] > s) {
// vis[r] = 0 ;
// r = f[r][0] ;
// vis[r] = 1 ;
// }else while (dis[r] - dis[l] <= s && l != 0) {
// l = f[l][0] ;vis[l] = 1 ;
// }int rlca ;
// for(int i = 1 ; i <= n ; i ++) {
// if(vis[i]) continue ;
// int lca1 = lca(l,i) , lca2 = lca(r,i) ;
// if(dep[lca1] > dep[lca2]) rlca = lca1 ;
// else rlca = lca2 ;
// if(dep[rlca] < dep[l]) {
// sum = max(sum,dis[i]-2*dis[rlca]) ;
// }else sum = max(sum,dis[i]-dis[rlca]) ;
// ans = min(ans,sum) ;
// l = f[l][0] ;
// vis[l] = 1 ;
// }
// }
while(l!=0)
{
sum=0;
if(dis[r]-dis[l]>s)
{
vis[r]=0;r=f[r][0];vis[r]=1;
}
else
{
while(dis[r]-dis[l]<=s&&l!=0) {l=f[l][0];vis[l]=1;}
int rlca;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
int lca1=lca(l,i),lca2=lca(r,i);
if(dep[lca1]>dep[lca2]) rlca=lca1;
else rlca=lca2;
if(dep[rlca]<dep[l])
{
sum=max(sum,dis[l]+dis[i]-2*dis[rlca]);
}
else sum=max(sum,dis[i]-dis[rlca]);
}
ans=min(ans,sum);
l=f[l][0];vis[l]=1;
}
}
cout << ans << endl ;
return 0;
}
//void dfs2(int u , int fa) {
// for(int i = head[u] ; i ; i = a[i].next) {
// int v = a[i].y ;
// if(v == fa) continue ;
// dis[v] = dis[u] + a[i].z ;
// f[v][0] = u ;
// dep[v] = dep[u] + 1 ;
// dfs2(v,u) ;
// }
//}
void dfs2(int k,int fa){
for(int i=head[k];i;i=a[i].next){
int v=a[i].y;
if(v==fa) continue;
dis[v]=dis[k]+a[i].z;f[v][0]=k;dep[v]=dep[k]+1;
dfs2(v,k);
}
}
//void dfs1(int u ,int fa) {
// for(int i = head[u] ; i ; i = a[i].next) {
// int v = a[i].y ;
// if(v == fa) continue ;
// dis[v] = a[i].z + dis[u] ;
// dfs1(v,u) ;
// }
//}
void dfs1(int k,int fa){
for(int i=head[k];i;i=a[i].next){
int v=a[i].y;
if(v==fa) continue;
dis[v]=dis[k]+a[i].z;
dfs1(v,k);
}
}
//int lca(int x , int y) {
// if(dep[x] < dep[y]) {
// swap(x,y) ;
// }
// for(int i = 20 ; i >= 0 ; i --) {
// if(dep[f[x][i]] >= dep[y]) x= f[x][i] ;
// }
// if(x == y) return x ;
// for(int i = 20 ; i >= 0 ; i --) {
// if(f[x][i] != f[y][i])
// x = f[x][i] , y = f[y][i] ;
// }
// return f[x][0] ;
//}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
}
if(x==y) return x;
for(int i=19;i>=0;i--)
{
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
//void init () {
// for(int i = 1 ; i <= 20 ; i ++){
// for(int j = 1 ; j <= n ; j ++) {
// f[j][i] = f[f[j][i-1]][i-1] ;
// }
// }
//}
void init()
{
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)
{
f[j][i]=f[f[j][i-1]][i-1];
}
}
}
//void add(int x , int y , int z) {
// a[++t].x = x ;
// a[t].y = y ;
// a[t].z = z ;
// a[t].next = head[x] ;
// head[x] = t ;
//}
void add(int x,int y,int z)
{
cnt++;
a[cnt].y=y;
a[cnt].next=head[x];
a[cnt].z=z;
head[x]=cnt;
}
int read() {
int x = 0;int f = 1 ; char s = getchar() ;
while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
return x*f ;
}
代码很乱,可能与L_Y_T的懒癌有关系…
凌乱的215行代码…
完结撒金坷垃!!
京公网安备 11010502036488号