做统计表的网站,怎么建立免费的网站,百度做个网站多少钱,做网站应该了解什么正题
题目链接:https://www.luogu.com.cn/problem/P5895 题目大意 nnn个点的一个森林#xff0c;加入若干条长度为LLL的边使它变成一个树#xff0c;求这棵树的最小直径。 解题思路
显然最优情况一定是以某个节点作为中间展开的一个菊花图#xff08;每棵树看做一个点加入若干条长度为LLL的边使它变成一个树求这棵树的最小直径。 解题思路
显然最优情况一定是以某个节点作为中间展开的一个菊花图每棵树看做一个点。
而且每个被连接的节点一定是树上的一个节点满足离它最远的节点最近。我们的定义这个距离为这棵树的半径rrr。
那么答案分为三种情况以下的rrr按照大小排序
某棵树的直径r1r2lr_1r_2lr1r2lr1r_1r1的树作为中心r2r_2r2连接这个点r2r3l∗2r_2r_3l*2r2r3l∗2r1r_1r1的树作为中心直径跨越这个中间点
然后树形dpdpdp求解即可时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
struct node{int to,next,w;
}a[N*2];
int l,n,m,ans,tot,cnt,tmp,r[N],g[N],f[N],ls[N],fr[N];
bool v[N];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(int x,int fa){v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);if(f[y]a[i].wf[x])g[x]f[x],f[x]f[y]a[i].w,fr[x]y;else if(f[y]a[i].wg[x])g[x]f[y]a[i].w;}ansmax(ans,f[x]g[x]);return;
}
void dp(int x,int fa){tmpmin(tmp,f[x]);for(int ils[x];i;ia[i].next){int ya[i].to,w;if(yfa)continue;if(yfr[x])wg[x]a[i].w;else wf[x]a[i].w;if(wf[y])g[y]f[y],f[y]w,fr[y]x;else if(wg[y])g[y]w;dp(y,x);}return;
}
int main()
{scanf(%d%d%d,n,m,l);for(int i1;im;i){ int x,y,w;scanf(%d%d%d,x,y,w);x;y;addl(x,y,w);addl(y,x,w);}for(int i1;in;i){if(v[i])continue;dfs(i,0);tmp2147483647;dp(i,0);r[cnt]tmp;}sort(r1,r1cnt);if(cnt2)ansmax(ans,r[cnt]r[cnt-1]l);if(cnt3)ansmax(ans,r[cnt-1]r[cnt-2]l*2);printf(%d\n,ans);return 0;
}
