1218 疫情控制

?

2012年NOIP全國聯(lián)賽提高組

?時間限制: 2 s ?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond 題解 ?查看運行結果 題目描述?Description

H?國有?n?個城市，這?n?個城市用?n-1?條雙向道路相互連通構成一棵樹，1?號城市是首都，

也是樹中的根節(jié)點。

H?國的首都爆發(fā)了一種危害性極高的傳染病。當局為了控制疫情，不讓疫情擴散到邊境

城市（葉子節(jié)點所表示的城市），決定動用軍隊在一些城市建立檢查點，使得從首都到邊境

城市的每一條路徑上都至少有一個檢查點，邊境城市也可以建立檢查點。但特別要注意的是，

首都是不能建立檢查點的。

現(xiàn)在，在?H國的一些城市中已經駐扎有軍隊，且一個城市可以駐扎多個軍隊。一支軍

隊可以在有道路連接的城市間移動，并在除首都以外的任意一個城市建立檢查點，且只能在

一個城市建立檢查點。一支軍隊經過一條道路從一個城市移動到另一個城市所需要的時間等

于道路的長度（單位：小時）。

請問最少需要多少個小時才能控制疫情。注意：不同的軍隊可以同時移動。

?

輸入描述?Input Description

第一行一個整數(shù)?n，表示城市個數(shù)。

接下來的?n-1?行，每行?3?個整數(shù)，u、v、w，每兩個整數(shù)之間用一個空格隔開，表示從

城市?u?到城市?v?有一條長為?w?的道路。數(shù)據保證輸入的是一棵樹，且根節(jié)點編號為?1。

接下來一行一個整數(shù)?m，表示軍隊個數(shù)。

接下來一行?m?個整數(shù)，每兩個整數(shù)之間用一個空格隔開，分別表示這?m?個軍隊所駐扎

的城市的編號。

輸出描述?Output Description

共一行，包含一個整數(shù)，表示控制疫情所需要的最少時間。如果無法控制疫情則輸出-1。

樣例輸入?Sample Input

4?

1?2?1?

1?3?2?

3?4?3?

2?

2?2?

樣例輸出?Sample Output

3

數(shù)據范圍及提示?Data Size & Hint

【輸入輸出樣例說明】

第一支軍隊在?2?號點設立檢查點，第二支軍隊從?2?號點移動到?3?號點設立檢查點，所需

時間為?3?個小時。

?

【數(shù)據范圍】

保證軍隊不會駐扎在首都。

對于?20%的數(shù)據，2≤?n≤?10；

對于?40%的數(shù)據，2?≤n≤50，0<w?<10^5；

對于?60%的數(shù)據，2?≤?n≤1000，0<w?<10^6；

對于?80%的數(shù)據，2?≤?n≤10,000；

對于?100%的數(shù)據，2≤m≤n≤50,000，0<w?<10^9。

分類標簽?Tags?點此展開?

大陸地區(qū)?NOIP全國聯(lián)賽提高組?2012年 題解：（tyts） 這道題主要算法就是貪心以及倍增和二分答案。首先我們對樹進行處理，記錄每個點2的次冪的father是誰，以及每個點到達根節(jié)點的距離是多少。我們發(fā)現(xiàn)對于當前的點，在給定的時間內只能往上走，因為往下走能看守的點會減少并且浪費時間。往下走的充要條件是到達了根節(jié)點，然后從根節(jié)點退下一格，到達另一個葉子。我們預處理每個節(jié)點如果看守住了，相當于看守住了最靠近根節(jié)點的哪個節(jié)點。我們發(fā)現(xiàn)如果一個點只有一個兒子，那么看守它的兒子也就相當于看守了它。 ?接下來我們考慮對于給定的時間k，如何檢驗它是否合法。我們把每一個有軍隊的節(jié)點向靠近根節(jié)點的方向走，直到不能走為止。如果一個軍隊沒有走到根節(jié)點，那么他顯然只能去看守最后到達的那個節(jié)點，這已經是最優(yōu)方案。接下來我們考慮對于到達根節(jié)點的所有點中，我們記錄每個點的兩個屬性：一是他來自哪里，二是他還能走多長時間的路。接下來的貪心策略是如果一個點的剩余路程不足以使得他回到他來自的哪個節(jié)點，我們則把他退回去，并且刪掉這樣的點。接下來我們把剩余到達根節(jié)點的點按照剩余路程從小到大排序，記為數(shù)組A，把根節(jié)點的葉子節(jié)點中沒有被覆蓋的節(jié)點取出，并且按照到達根節(jié)點的距離進行從小到大排序，記為數(shù)組B。最后我們把兩個數(shù)組進行歸并，用A中小的去覆蓋B中小的，如果B可以被完全覆蓋則當前的k合法，否則不合法。時間復雜度為O(nlognlogAns)。 ps：順便復習一下倍增lca? #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; #define N 100010 #define ll long long #define xx first #define yy second typedef pair<int,int> diy; inline const int read(){register int x=0,f=1;register char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline const char in(){for(register char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')) return ch; } struct ss{int v,w,next; }e[N<<1]; struct node{int u,v; }b[N],c[N]; int tot,head[N]; int dep[N],f[N][21],g[N][21],a[N]; bool vis[N]; int n,m,l,r,mid; void add(int x,int y,int z){e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot; } bool cmp(const node &a,const node &b){return a.v<b.v;//因為我們要控制所有葉子節(jié)點，也就是所有的1的兒子，所以我們把剩余的軍隊和剩余的1的兒子拉出來，排個序，貪心地匹配。 } void dfs(int x,int y){for(int i=head[x];i;i=e[i].next){if(e[i].v!=y){f[e[i].v][0]=x;//f[i][0]保存i的父節(jié)點為xg[e[i].v][0]=e[i].w;//同步記錄該邊的權值 dep[e[i].v]=dep[x]+1;//當前點深度+1 dfs(e[i].v,x);}} } int lca(int a,int b){//從深度大的節(jié)點上升至深度小的節(jié)點同層，如果此時兩節(jié)點相同直接返回此節(jié)點，即lca。 //否則，利用倍增法找到最小深度的: g[x][j]!=g[y][j]，此時他們的父親g[x][0]即lca。if(dep[a]<dep[b]) swap(a,b);int t=dep[a]-dep[b];for(int i=0;i<=20;i++){if((1<<i)&t){a=f[a][i];}}if(a==b) return a;for(int i=20;i>=0;i--){//倍增法，每次向上進深度2^j，找到最近公共祖先的子結點if(f[a][i]!=f[b][i]){a=f[a][i];b=f[b][i];}}return f[a][0]; } void color(int x){//如果不能到達1點，那就停在最高點 bool p=1,q=0;for(int i=head[x];i;i=e[i].next){if(e[i].v!=f[x][0]){color(e[i].v);p&=vis[e[i].v];q=1;}}if(p&&q&&x!=1) vis[x]=1; } bool check(int x){memset(vis,0,sizeof vis);int cnt=0,top=0;for(int i=1;i<=m;i++){//枚舉每一個軍隊可以上跳到哪個祖先int y=a[i],z=0,k=a[i];for(int j=20;j>=0;j--){if(f[y][j]&&z+g[y][j]<=x){z+=g[y][j];y=f[y][j];}}if(y!=1) vis[y]=1;else{//如果一個軍隊能夠到達1，也就能夠直接到達它所屬的那個1的兒子，所以每個軍隊就有兩個決策，也是貪心b[++cnt].v=x-z;//軍隊移動的距離 y=a[i];for(int j=20;j>=0;j--){//再往下找 if(f[y][j]>1){y=f[y][j];}}b[cnt].u=y;}}color(1);//我們對于不能跳到1點的軍隊就讓他停在最高點。for(int i=head[1];i;i=e[i].next){if(!vis[e[i].v]){c[++top].u=e[i].v;c[top].v=e[i].w;}}sort(b+1,b+cnt+1,cmp);//升序：剩余路程 sort(c+1,c+top+1,cmp);//升序：到根節(jié)點的距離（沒有覆蓋的跟的葉子節(jié)點） int j=1;c[top+1].v=0x3f3f3f3f;//限制 for(int i=1;i<=cnt;i++){if(!vis[b[i].u]) vis[b[i].u]=1;else if(b[i].v>=c[j].v) vis[c[j].u]=1;while(vis[c[j].u]) j++;}return j>top;//能否往上跳 } int main(){n=read();for(int i=1,x,y,z;i<n;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),r+=z;m=read();for(int i=1;i<=m;i++) a[i]=read();dfs(1,1);for(int j=1;j<=20;j++){//初始各個點的2^j祖先是誰 ,其中 2^j (j =0...log(該點深度))倍祖先，1倍祖先就是父親，2倍祖先是父親的父親......。for(int i=1;i<=n;i++){//f[i][j]表示i結點的第2^j祖先f[i][j]=f[f[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先g[i][j]=g[f[i][j-1]][j-1]+g[i][j-1];}}while(l<r){//答案在 0-所有邊權值的和 之中 mid=(l+r>>1);if(check(mid)) r=mid;else l=mid+1;}printf("%d\n",check(l)?l:-1);return 0; }

?

轉載于:https://www.cnblogs.com/shenben/p/5652552.html

總結

以上是生活随笔為你收集整理的1218 疫情控制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。