傳送門

最近搞一搞樹型結(jié)構(gòu)……畢竟自己樹的知識(shí)學(xué)的太垃圾了。

首先這道題非常明顯要求樹的直徑。樹的直徑有好多好多種求法，這里我選擇了一位dalao的非常簡(jiǎn)潔的dfs的方法。先看一下代碼。

void dfs(int x) {for(int i = head[x];i;i = e[i].next){if(fa[x] == e[i].to || vis[e[i].to]) continue;fa[e[i].to] = x;dis[e[i].to] = dis[x] + e[i].v;dfs(e[i].to);} }

代碼非常的簡(jiǎn)短。具體的思想也很好理解，就是依次向下dfs，然后使用fa來記錄在直徑上都有哪些點(diǎn)。不過這個(gè)使用的時(shí)候要注意，就是每次要被開始進(jìn)行搜索的那個(gè)點(diǎn)的dis賦成0.

思想就是兩遍dfs。第一遍先隨便搜，搜到一個(gè)與之相距最遠(yuǎn)的點(diǎn)（這個(gè)點(diǎn)必然是樹的直徑之一），之后再從這個(gè)點(diǎn)進(jìn)行dfs，之后搜到一個(gè)與之距離最遠(yuǎn)的點(diǎn)（直徑的另一個(gè)端點(diǎn)），這就是樹的直徑了。

然后怎么做？

我們可以使用直徑的性質(zhì)。首先來看偏心距的定義，對(duì)于一條路徑F，樹中與之距離最遠(yuǎn)的點(diǎn)到路徑F的距離為F的偏心距。首先每條直徑肯定會(huì)有一個(gè)最小的偏心距，所以只要求一條直徑就可以啦。

之后，我們要求偏心距最小……首先我們通過直徑的性質(zhì)可以知道一件事，就是對(duì)于直徑上一條路徑的偏心距，一定是當(dāng)前這條路徑的兩端點(diǎn)到直徑兩端點(diǎn)距離的最大值。這個(gè)必然成立，否則肯定存在一條比你當(dāng)前求的直徑還長(zhǎng)的一條鏈。

那么我們就可以使用貪心的思想，每次在直徑上取一條長(zhǎng)度不大于限制條件的路徑，之后每次更新最小偏心距即可。注意有一種特殊情況就是直徑的總長(zhǎng)要小于限制的長(zhǎng)度，這時(shí)就從每個(gè)在直徑上的點(diǎn)開始dfs，最后輸出最大的值就好啦。

看一下代碼。

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar('\n')using namespace std; typedef long long ll; const int M = 5000005; const int INF = 1000000009;int read() {int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op; }struct node {int next,to,v; }e[M<<1];int n,s,x,y,ecnt,head[M],dis[M],fa[M],r1,r2,ans = INF,k,z; bool vis[M];void add(int x,int y,int z) {e[++ecnt].to = y;e[ecnt].v = z;e[ecnt].next = head[x];head[x] = ecnt; }void dfs(int x) {for(int i = head[x];i;i = e[i].next){if(fa[x] == e[i].to || vis[e[i].to]) continue;fa[e[i].to] = x;dis[e[i].to] = dis[x] + e[i].v;dfs(e[i].to);} } void solve() {ans = -1;for(int i = r2;i;i = fa[i]) vis[i] = 1;for(int i = r2;i;i = fa[i]) dis[i] = 0,dfs(i);rep(i,1,n) ans = max(ans,dis[i]);printf("%d\n",ans); } int main() {n = read(),s = read();rep(i,1,n-1) x = read(),y = read(),z = read(),add(x,y,z),add(y,x,z);dfs(1);memset(fa,0,sizeof(fa));rep(i,1,n) if(dis[i] > dis[r1]) r1 = i;//找到第一個(gè)端點(diǎn)dis[r1] = 0,dfs(r1);rep(i,1,n) if(dis[i] > dis[r2]) r2 = i;//找到第二個(gè)端點(diǎn)k = r2;if(dis[k] <= s){solve();//直徑長(zhǎng)度小于限制長(zhǎng)度的解決return 0;}for(int i = r2;i;i = fa[i]){while(fa[k] && dis[i] - dis[fa[k]] <= s) k = fa[k];//貪心取鏈ans = min(ans,max(dis[k],dis[r2] - dis[i]));//更新最小偏心距 }printf("%d\n",ans);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/captain1/p/9636634.html

總結(jié)

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

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