【題目描述】

設(shè)T=(V, E, W) 是一個(gè)無(wú)圈且連通的無(wú)向圖（也稱(chēng)為無(wú)根樹(shù)），每條邊帶有正整數(shù)的權(quán)，我們稱(chēng)T為樹(shù)網(wǎng)（treenetwork），其中V, E分別表示結(jié)點(diǎn)與邊的集合，W表示各邊長(zhǎng)度的集合，并設(shè)T有n個(gè)結(jié)點(diǎn)。

路徑：樹(shù)網(wǎng)中任何兩結(jié)點(diǎn)a,b都存在唯一的一條簡(jiǎn)單路徑，用d(a,b)表示以a,b為端點(diǎn)的路徑的長(zhǎng)度，它是該路徑上各邊長(zhǎng)度之和。我們稱(chēng)d(a,b)為a,b兩結(jié)點(diǎn)間的距離。

一點(diǎn)v到一條路徑P的距離為該點(diǎn)與P上的最近的結(jié)點(diǎn)的距離：

d(v，P)=min{d(v，u)，u為路徑P上的結(jié)點(diǎn)}。

樹(shù)網(wǎng)的直徑：樹(shù)網(wǎng)中最長(zhǎng)的路徑稱(chēng)為樹(shù)網(wǎng)的直徑。對(duì)于給定的樹(shù)網(wǎng)T，直徑不一定是唯一的，但可以證明：各直徑的中點(diǎn)（不一定恰好是某個(gè)結(jié)點(diǎn)，可能在某條邊的內(nèi)部）是唯一的，我們稱(chēng)該點(diǎn)為樹(shù)網(wǎng)的中心。

偏心距ECC(F)：樹(shù)網(wǎng)T中距路徑F最遠(yuǎn)的結(jié)點(diǎn)到路徑F的距離， 即 ECC(F)=max{d(v,F),v∈V}.

任務(wù)：對(duì)于給定的樹(shù)網(wǎng)T=(V, E,W)和非負(fù)整數(shù)s，求一個(gè)路徑F，它是某直徑上的一段路徑（該路徑兩端均為樹(shù)網(wǎng)中的結(jié)點(diǎn)），其長(zhǎng)度不超過(guò)s（可以等于s），使偏心距ECC(F)最小。我們稱(chēng)這個(gè)路徑為樹(shù)網(wǎng)T=(V,E,W)的核（Core）。必要時(shí)，F可以退化為某個(gè)結(jié)點(diǎn)。一般來(lái)說(shuō)，在上述定義下，核不一定只有一個(gè)，但最小偏心距是唯一的。

下面的圖給出了樹(shù)網(wǎng)的一個(gè)實(shí)例。圖中，A-B與A-C是兩條直徑，長(zhǎng)度均為20。點(diǎn)W是樹(shù)網(wǎng)的中心，EF邊的長(zhǎng)度為5。如果指定s=11，則樹(shù)網(wǎng)的核為路徑DEFG（也可以取為路徑DEF），偏心距為8。如果指定s=0（或s=1、s=2），則樹(shù)網(wǎng)的核為結(jié)點(diǎn)F，偏心距為12。

【輸入格式】

輸入文件包含n行：
第1行，兩個(gè)正整數(shù)n和s，中間用一個(gè)空格隔開(kāi)。其中n為樹(shù)網(wǎng)結(jié)點(diǎn)的個(gè)數(shù)，s為樹(shù)網(wǎng)的核的長(zhǎng)度的上界。設(shè)結(jié)點(diǎn)編號(hào)依次為1, 2, ..., n。
從第2行到第n行，每行給出3個(gè)用空格隔開(kāi)的正整數(shù)，依次表示每一條邊的兩個(gè)端點(diǎn)編號(hào)和長(zhǎng)度。例如，“2 4 7”表示連接結(jié)點(diǎn)2與4的邊的長(zhǎng)度為7。
所給的數(shù)據(jù)都是正確的，不必檢驗(yàn)。

【輸出格式】

輸出文件只有一個(gè)非負(fù)整數(shù)，為指定意義下的最小偏心距。

【樣例輸入】

5 2
1 2 5
2 3 2
2 4 4
2 5 3

【樣例輸出】

5
【分析】

首先找到一個(gè)樹(shù)的直徑。方法是：從1點(diǎn)出發(fā)，找到距離1最遠(yuǎn)的點(diǎn)，記為x。然后從x出發(fā)，所搜索到的最遠(yuǎn)路徑就是樹(shù)的直徑。

然后我們用搜索的方法計(jì)算每個(gè)點(diǎn)到直徑的最短距離dist。

之后在直徑上枚舉路徑的起點(diǎn)和終點(diǎn)。找到最小的偏心距。

#include <stdio.h> #include <string.h> #include <limits.h> #define MAXN 310 struct tnode {int num;tnode *next; } g[MAXN],*t; int q[MAXN * 3],list[MAXN],loc[MAXN],dist[MAXN],from[MAXN],dis[MAXN],di[MAXN][MAXN],xdis[MAXN][MAXN]; int n,l,r,s,x,y,z,tot,ans; bool v[MAXN],in_tree[MAXN]; void insert(int x,tnode &p) {t = new(tnode);t->num = x;t->next = p.next;p.next = t; } void dfs(int father,int x) {tnode *tt;tt = g[x].next;while (tt != NULL) {int y = tt->num;if (!in_tree[y])if (dist[x] + di[x][y] < dist[y]) {dist[y] = dist[x] + di[x][y];from[y] = father;dfs(father,y);}tt = tt->next;} } int main() { scanf("%d%d",&n,&s);for (int i = 1;i < n;++i) {scanf("%d%d%d",&x,&y,&z);insert(x,g[y]);insert(y,g[x]);di[x][y] = z;di[y][x] = z;}q[0] = 1;v[1] = 1;while (l <= r) {x = q[l];t = g[x].next;while (t != NULL) {y = t->num;if (y != from[x])if (dis[y] < di[x][y] + dis[x]) {dis[y] = di[x][y] + dis[x];from[y] = x;if (!v[y]) {q[++r] = y;v[y] = 1;}}t = t->next;}++l;v[x] = 0;}z = 0;for (int i = 1;i <= n;++i)if (dis[i] > z) {z = dis[i];x = i;}memset(from,0,sizeof(from));memset(v,0,sizeof(v));v[x] = 1;memset(dis,0,sizeof(dis));q[0] = x;v[x] = 1;l = r = 0;while (l <= r) {x = q[l];t = g[x].next;while (t != NULL) {y = t->num;if (from[x] != y)if (dis[y] < di[x][y] + dis[x]) {dis[y] = di[x][y] + dis[x];from[y] = x;if (!v[y]) {q[++r] = y;v[y] = 1;}}t = t->next;}++l;v[x] = 0;}z = 0;for (int i = 1;i <= n;++i)if (dis[i] > z) {z = dis[i];x = i;}list[++tot] = x;while (from[x]) {x = from[x];list[++tot] = x;}for (int i = 1;i <= tot;++i) {loc[list[i]] = i;in_tree[list[i]] = 1;}for (int i = 1;i <= tot;++i)for (int j = i + 1;j <= tot;++j)xdis[i][j] = xdis[i][j - 1] + di[list[j - 1]][list[j]];memset(from,0,sizeof(from));for (int i = 1;i <= n;++i)if (!in_tree[i])dist[i] = INT_MAX;for (int i = 1;i <= tot;++i)dfs(list[i],list[i]);ans = INT_MAX;for (int st = 1;st <= tot;++st)for (int en = st;en <= tot;++en) {if (xdis[st][en] > s)break;int te_ans = 0;for (int i = 1;i <= n;++i)if (!in_tree[i]) {if (dist[i] > te_ans)te_ans = dist[i];} else {x = loc[i];if (x < st) {if (dist[i] + xdis[x][st] > te_ans)te_ans = dist[i] + xdis[x][st];}if (x > en) {if (dist[i] + xdis[en][x] > te_ans)te_ans = dist[i] + xdis[en][x];}}if (te_ans < ans)ans = te_ans;}printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/sephirothlee/archive/2010/10/14/1850939.html

總結(jié)

以上是生活随笔為你收集整理的[O(N)的我不会]树网的核的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。