简答题 偏难
#23621

树网的核 【问题描述】 设 T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 T 为树网(treenetwork)…

树网的核

【问题描述】

设 T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 T 为树网(treenetwork),其中 V, E 分别表示结点与边的集合,W 表示各边长度的集合,并设 T 有 n 个结点。

路径:树网中任何两结点 a,b 都存在唯一的一条简单路径,用 d(a,b)表示以 a,b 为端点的路径的长度,它是该路径上各边长度之和。我们称 d(a,b)为 a,b 两结点间的距离。一点 v 到一条路径 P 的距离为该点与 P 上的最近的结点的距离:

d(v,P)=min{d(v,u),u 为路径 P 上的结点}。

树网的直径:树网中最长的路径称为树网的直径。对于给定的树网 T,直径不一定是唯一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一的,我们称该

点为树网的中心。

偏心距 ECC(F):树网 T 中距路径 F 最远的结点到路径 F 的距离,即

任务:对于给定的树网 T=(V, E,W)和非负整数 s,求一个路径 F,它是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过 s(可以等于 s),使偏心距 ECC(F)最小。我们称这个路径为树网 T=(V,E,W)的核(Core)。必要时,F 可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中,A-B 与 A-C 是两条直径,长度均为 20。点 W 是树网的中心,EF 边的长度为 5。如果指定 s=11,则树网的核为路径 DEFG(也可以取为路径 DEF),偏心距为 8。如果指定 s=0(或 s=1、s=2),则树网的核为结点 F,偏心距为 12。

【输入】

 输入文件 core.in 包含 n 行:

第 1 行,两个正整数 n 和 s,中间用一个空格隔开。其中 n 为树网结点的个数,s 为树网的核的长度的上界。设结点编号依次为 1, 2, ..., n。

从第 2 行到第 n 行,每行给出 3 个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。例如,“2 4 7”表示连接结点 2 与 4 的边的长度为 7。

所给的数据都是正确的,不必检验。

【输出】

 输出文件 core.out 只有一个非负整数,为指定意义下的最小偏心距。

【输入输出样例 1】

【输入输出样例 2】

【限制】

 40%的数据满足:5<=n<=15

 70%的数据满足:5<=n<=80

 100%的数据满足:5<=n<=300, 0<=s<=1000。边长度为不超过 1000 的正整数

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</p><p style="text-align: left;">#include&lt;cstring&gt;</p><p style="text-align: left;">const int inf=0x3f3f3f3f;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">int n,s,a,b,c,maxx=0,mxi,mxj;</p><p style="text-align: left;">int dis[305][305];</p><p style="text-align: left;">int read(){</p><p style="text-align: left;">    int ans=0,f=1;char c=getchar();</p><p style="text-align: left;">    while(c&lt;'0'||c&gt;'9'){</p><p style="text-align: left;">    <span style="white-space:pre"> </span>if(c=='-')f=-1;</p><p style="text-align: left;">    <span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;">    }</p><p style="text-align: left;">    while(c&gt;='0'&amp;&amp;c&lt;='9'){</p><p style="text-align: left;">    <span style="white-space:pre"> </span>ans=ans*10+c-48;</p><p style="text-align: left;">    <span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return ans*f;</p><p style="text-align: left;">} </p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    n=read();s=read();</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">        for(int j=1;j&lt;=n;j++)</p><p style="text-align: left;">            if(i!=j)dis[i][j]=inf;</p><p style="text-align: left;">    for(int i=1;i&lt;=n-1;i++){</p><p style="text-align: left;">        a=read();b=read();c=read();dis[a][b]=dis[b][a]=c;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for(int k=1;k&lt;=n;k++)</p><p style="text-align: left;">        for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">            for(int j=1;j&lt;=n;j++){</p><p style="text-align: left;">                if(dis[i][k]&gt;=inf||dis[k][j]&gt;=inf)continue;</p><p style="text-align: left;">                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);</p><p style="text-align: left;">                if(dis[i][j]&gt;maxx){</p><p style="text-align: left;">                    maxx=dis[i][j];</p><p style="text-align: left;">                    mxi=i;mxj=j;</p><p style="text-align: left;">                }</p><p style="text-align: left;">            }</p><p style="text-align: left;">    int ans=inf;</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++){</p><p style="text-align: left;">        if(dis[mxi][i]+dis[i][mxj]!=dis[mxi][mxj])continue;</p><p style="text-align: left;">        for(int j=1;j&lt;=n;j++){</p><p style="text-align: left;">            if(dis[mxi][j]+dis[j][mxj]!=dis[mxi][mxj]||dis[i][j]&gt;s)continue;</p><p style="text-align: left;">            int ecc=0;</p><p style="text-align: left;">            ecc=max(min(dis[mxi][i],dis[mxi][j]),min(dis[mxj][i],dis[mxj][j]));</p><p style="text-align: left;">            ans=min(ans,ecc);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    printf("%d",ans);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。