【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=b704 &&http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1999
【題意】 給你一棵樹(shù); 讓你找出所有的直徑; 并在這些直徑上面選取連續(xù)的一段; 使得它的偏心距最小;
【題解】 這題有個(gè)思維量比較大的點(diǎn)就是; 多條直徑,只要選取任意一條就好; 網(wǎng)上找到了很多分析; 感覺(jué)這個(gè)說(shuō)得比較清楚吧;
/*證明：首先，如圖，如果ABCD和FBCE都是直徑的話，則AB=FB，CD=CE（如果不然，可設(shè)AB>FB，則FBCE<ABCE，矛盾?。?。這樣，ABCE，F(xiàn)BCD也都是直徑。我們給BC起個(gè)名字叫“公共段”。由連通性和路徑的不唯一性，公共段必然存在?？紤]ecc的定義，路徑的ecc是指所有的點(diǎn)到路徑的距離的最大值。核指的是直徑上長(zhǎng)度滿足約束的ECC最小的子路經(jīng)。假如根據(jù)直徑ABCE算得的core是GHBI，路徑GHBI的ecc就是max{BF,AG,DI, EI},這個(gè)最大值取到了最小。由于DC=EC，也就是說(shuō)，如果路徑和公共段有交集，公共段的一端上，不包含CORE的直徑是可以任選的。換言之，如果max{BF,AG,DI, EI}取到了最小值，必有 max{BF,AG,ID}=max{BF,AG,DI, EI}，此時(shí)用AB替換BF，則BF=AB>AG，ecc=max{BF,ID}。也就是說(shuō)，如果路徑和公共段有交集，實(shí)際計(jì)算max時(shí)，只需要計(jì)算路徑在公共段上的部分的ecc，然后和公共段兩端的路徑長(zhǎng)取一遍MAX就行了。下面證明，使得ecc取到最小的core必然和公共段有交集。設(shè)沒(méi)有交集，則必然有一條直徑和這個(gè)core沒(méi)有交集，此core的ecc就至少嚴(yán)格大于公共段長(zhǎng)度+除去公共段的半條路徑長(zhǎng)度，然而，公共段上的點(diǎn)到其他點(diǎn)的最長(zhǎng)距離，最大不會(huì)大于這個(gè)長(zhǎng)度，這與ecc最小矛盾！通過(guò)上面的論述，得出core只與公共段有關(guān)，也就是說(shuō)引理成立。所以在計(jì)算時(shí)任選一條直徑即可，}*/知道上面這個(gè)結(jié)論之后,瞬間壓力就小了很多了; 再貪心一下; 可以想見(jiàn),肯定是這段路徑的長(zhǎng)度越長(zhǎng)越好; (如果不是最長(zhǎng)的,那么就會(huì)有一段多出來(lái),所以感覺(jué)上是盡可能地長(zhǎng)) 所以每次枚舉這段路徑的起點(diǎn),終點(diǎn)的話可以根據(jù)s來(lái)確定,越長(zhǎng)越好; 當(dāng)然在枚舉之前,先找出任意一條直徑;然后把直徑上的點(diǎn)標(biāo)記一下; 然后從直徑上的點(diǎn)開(kāi)始進(jìn)行dfs;在不經(jīng)過(guò)直徑的情況下,看看這個(gè)點(diǎn)最遠(yuǎn)能走多遠(yuǎn);則這個(gè)長(zhǎng)度就是這個(gè)點(diǎn)的偏心距了; (整條直徑的偏心距就是這個(gè)直徑上的所有的點(diǎn)的偏心距的最大值->直徑的偏心距的等價(jià)含義); 這個(gè)可以預(yù)處理出來(lái);->設(shè)為mmax[n] 然后回到枚舉那段 枚舉了起點(diǎn)s,和終點(diǎn)t; 然后直徑的左端點(diǎn)為l,右端點(diǎn)為r; 則這段路徑s..t的偏心距為max(dis[l]-dis[s],dis[r]-dis[t],mmax[s..t]中的最大值); (dis[x]是這段路徑上的點(diǎn)x到直徑的左端點(diǎn)l的距離); 因?yàn)樵谇髆max的時(shí)候沒(méi)有考慮直徑上的點(diǎn),所以會(huì)漏掉這種情況.就是直徑的左端點(diǎn)和右端點(diǎn)離這個(gè)核最遠(yuǎn)的情況. 這里s..t可以像窗口一樣往右移動(dòng); (保持前一次的右端點(diǎn)t不動(dòng),左端點(diǎn)右移,然后根據(jù)新的左端點(diǎn)調(diào)整右端點(diǎn)); 可以想到用單調(diào)隊(duì)列來(lái)優(yōu)化; 這里dis[l]-dis[s],dis[r]-dis[t]都是定值了,所以不用管; 直接維護(hù)mmax單調(diào)遞減就好; (求直徑的話,隨便從一個(gè)點(diǎn)開(kāi)始dfs,找離他最遠(yuǎn)的點(diǎn)u1,然后從u1再重復(fù)上述過(guò)程,找到u2,則u1-u2就是一條直徑); 【完整代碼】
#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 5e5+100;struct abc{ int nex,en,w;};int dis[MAXN],n,s,tot,fir[MAXN],path[MAXN],len,lmax[MAXN],rmax[MAXN],mmax[MAXN];int dl[MAXN],l,r;bool bo[MAXN];abc bian[MAXN*2];void add(int x,int y,int z){ bian[++tot].nex = fir[x]; fir[x] = tot; bian[tot].en = y,bian[tot].w = z;}void dfs(int x,int fa,int arr[]){ for (int i = fir[x];i;i=bian[i].nex) { int y = bian[i].en; if (y==fa) continue; arr[y] = arr[x] + bian[i].w; dfs(y,x,arr); }}bool get_path(int x,int aim,int fa){ if (x==aim) { path[++len] = x; return true; } for (int i = fir[x];i;i=bian[i].nex) { int y = bian[i].en; if (y==fa) continue; if (get_path(y,aim,x)) { path[++len] = x; return true; } } return false;}int gainecc(int x,int fa){ int ret = 0; for (int i = fir[x];i;i = bian[i].nex) { int y = bian[i].en; if (bo[y] || y==fa) continue; ret = max(gainecc(y,x)+bian[i].w,ret); } return ret;}int main(){ //freopen("F://rush.txt","r",stdin); rei(n);rei(s); rep1(i,1,n-1) { int x,y,z; rei(x);rei(y);rei(z); add(x,y,z),add(y,x,z); } int q,w; dis[1] = 0; dfs(1,0,dis); q = 1; rep1(i,2,n) if (dis[i]>dis[q]) q = i; dis[q] = 0; dfs(q,0,dis); w = 1; rep1(i,2,n) if (dis[i]>dis[w]) w = i; get_path(w,q,0); rep1(i,1,len) { lmax[i] = dis[path[i]]-dis[q]; rmax[i] = dis[w]-dis[path[i]]; } rep1(i,1,len) bo[path[i]] = true; rep1(i,1,len) mmax[path[i]] = gainecc(path[i],0); l = 1,r = 0; int j = 0,ans = -1; rep1(i,1,len) { while (j+1<=len && dis[path[j+1]]-dis[path[i]]<=s) { j++; while (r>=l && mmax[path[j]]>=mmax[path[dl[r]]]) r--; dl[++r] = j; } while (dl[l] < i) l++; int cal = max(mmax[path[dl[l]]],max(lmax[i],rmax[j])); if (ans == -1 || cal < ans) ans = cal; } printf("%d/n",ans); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
