貪心 排序 分治-二分答案
題目描述
H 國有 n 個城市，這 n 個城市用 n-1 條雙向道路互相連通構成一棵樹，1 号城市是首都，
也是樹中的根節點。
H 國的首都爆發了一種危害性極高的傳染病。當局為了控制疫情，不讓疫情擴散到邊境
城市（葉子節點所表示的城市），決定動用軍隊在一些城市建立檢查點，使得從首都到邊境
城市的每一條路徑上都至少有一個檢查點，邊境城市也可以建立檢查點。但特别要注意的是，
首都是不能建立檢查點的。
現在，在 H 國的一些城市中已經駐紮有軍隊，且一個城市可以駐紮多個軍隊。一支軍隊可以在有道路連接配接的城市間移動，并在除首都以外的任意一個城市建立檢查點，且隻能在
一個城市建立檢查點。一支軍隊經過一條道路從一個城市移動到另一個城市所需要的時間等
于道路的長度（機關：小時）。
請問最少需要多少個小時才能控制疫情。注意：不同的軍隊可以同時移動。
輸入輸出格式
輸入格式：
第一行一個整數 n，表示城市個數。
接下來的 n-1 行，每行 3 個整數，u、v、w，每兩個整數之間用一個空格隔開，表示從
城市 u 到城市 v 有一條長為 w 的道路。資料保證輸入的是一棵樹，且根節點編号為 1。
接下來一行一個整數 m，表示軍隊個數。
接下來一行 m 個整數，每兩個整數之間用一個空格隔開，分别表示這 m 個軍隊所駐紮
的城市的編号。
輸出格式：
共一行，包含一個整數，表示控制疫情所需要的最少時間。如果無法控制疫情則輸出-1。
輸入輸出樣例
輸入樣例#1：
4
1 2 1
1 3 2
3 4 3
2
2 2 輸出樣例#1：
3 說明
【輸入輸出樣例說明】
第一支軍隊在 2 号點設立檢查點，第二支軍隊從 2 号點移動到 3 号點設立檢查點，所需
時間為 3 個小時。
【資料範圍】
保證軍隊不會駐紮在首都。
對于 20%的資料，2≤ n≤ 10；
對于 40%的資料，2 ≤n≤50，0<w <10^5；
對于 60%的資料，2 ≤ n≤1000，0<w <10^6；
對于 80%的資料，2 ≤ n≤10,000；
對于 100%的資料，2≤m≤n≤50,000，0<w <10^9。
NOIP 2012 提高組 第二天 第三題
二分答案，看能否全部覆寫。
在限定的時間内，所有軍隊全速向首都行進。無法到達首都的軍隊要駐紮在盡可能近的位置（以盡可能控制更多邊緣城市），能到達首都的軍隊，要根據其剩餘時間選擇支援哪個城市（隻要走到首都的第一層子結點就能控制其下的所有邊緣城市），或者選擇幹脆不到達首都，直接駐紮在其來路的離首都最近城市。
↑以上操作可以用LCA便捷實作。
将所有可用軍隊的剩餘時間從小到大排序，将所有需要支援結點的距離從小到大排序，貪心選擇軍隊去支援即可。
1 /*by SilverN*/
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdio>
6 #include<cmath>
7 #define LL long long
8 #define fou(x,i,j) for(int x=i;x<=j;++x)
9 #define fo(x,i,j) for(int x=i;x>=j;--x)
10 using namespace std;
11 const int mxn=50005;
12 int read(){
13 int x=0,f=1;char ch=getchar();
14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
16 return x*f;
17 }
18 LL readL(){
19 LL x=0,f=1;char ch=getchar();
20 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
21 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
22 return x*f;
23 }
24 struct edge{
25 int v,nxt;
26 LL dis;
27 }e[mxn<<1];
28 int hd[mxn],mct=0;
29 void add_edge(int u,int v,LL dis){
30 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].dis=dis;hd[u]=mct;
31 return;
32 }
33 //
34 int n,m;
35 int pos[mxn];
36 //
37 int dep[mxn];
38 LL dis[mxn];
39 int fa[mxn][17];
40 void DFS(int u,int ff){
41 dep[u]=dep[ff]+1;
42 for(int i=hd[u];i;i=e[i].nxt){
43 int v=e[i].v;
44 if(v==ff)continue;
45 fa[v][0]=u;
46 dis[v]=dis[u]+e[i].dis;
47 DFS(v,u);
48 }
49 return;
50 }
51 void LCA_init(){
52 fou(i,1,16)
53 fou(j,1,n)
54 fa[j][i]=fa[fa[j][i-1]][i-1];
55 return;
56 }
57 struct cme{
58 int come;
59 LL dis;
60 }ari[mxn];//上溯時間
61 int cnt;
62 int cmp1(const cme a,const cme b){return a.dis<b.dis;}
63 struct tpro{
64 int city,dis;
65 }c[mxn];
66 int cmp2(const tpro a,const tpro b){return a.dis<b.dis;}
67 int cct=0;
68 //
69 int nps[mxn];
70 bool pro[mxn];//受保護的城市
71 void find(int u,int ff){
72 if(!e[hd[u]].nxt)return;
73 bool flag=1;
74 for(int i=hd[u];i;i=e[i].nxt){
75 int v=e[i].v;
76 if(v==ff)continue;
77 // printf("u %d to %d %d\n",u,v,pro[v]);
78 if(pro[v]){continue;}
79 find(v,u);
80 if(!pro[v])flag=0;
81 }
82 pro[u]=flag;
83 return;
84 }
85
86 bool solve(LL lim){
87 // printf("\n\ntest lim:%d\n",lim);
88 memset(pro,0,sizeof pro);
89 memset(ari,0,sizeof ari);
90 memcpy(nps,pos,sizeof pos);
91 cnt=0;cct=0;
92 for(int i=1;i<=m;i++){
93 if(dis[nps[i]]>lim){//時間不夠回到首都
94 LL lft=dis[nps[i]]-lim;
95 // printf("%d left:%d\n",i,lft);
96 fo(j,16,0)
97 if(dis[fa[nps[i]][j]]>=lft)
98 nps[i]=fa[nps[i]][j];
99 pro[nps[i]]=1;
100 // printf("num %d protected %d\n",i,nps[i]);
101 }
102 else{//時間夠回到首都
103 ari[++cnt].dis=lim-dis[nps[i]];
104 fo(j,16,0){
105 // printf("%d %d %d\n",fa[nps[i]][j],dep[fa[nps[i]][j]],nps[i]);
106 if(dep[fa[nps[i]][j]]>1)nps[i]=fa[nps[i]][j];
107 }
108 ari[cnt].come=nps[i];
109 // printf("%d comes from :%d\n",i,nps[i]);
110 }
111 }
112 find(1,0);
113 // printf("fin1\n");
114 if(pro[1])return true;
115 // printf("nxt:\n");
116 for(int i=hd[1];i;i=e[i].nxt){
117 int v=e[i].v;
118 if(!pro[v]) c[++cct].city=v,c[cct].dis=e[i].dis;
119 }
120 sort(ari+1,ari+cnt+1,cmp1);
121 sort(c+1,c+cct+1,cmp2);
122 /* printf("tpro:\n");
123 for(int i=1;i<=cct;i++){
124 printf("%d ",c[i].city);
125 }
126 printf("\n");*/
127 int j=1;
128 for(int i=1;i<=cnt;i++){
129 if(!pro[ari[i].come]){
130 pro[ari[i].come]=1;
131 continue;
132 }
133 while(pro[c[j].city] && j<=cct)j++;
134 if(c[j].dis<=ari[i].dis)pro[c[j].city]=1,++j;
135 }
136 for(int i=1;i<=cct;i++){
137 if(!pro[c[i].city])return false;
138 }
139 return true;
140 }
141 LL ans=1e11;
142 int main(){
143 n=read();
144 int i,j,u,v,w;
145 LL smm=0;
146 for(i=1;i<n;++i){
147 u=read();v=read();w=readL();
148 add_edge(u,v,w);
149 add_edge(v,u,w);
150 smm+=w;
151 }
152 DFS(1,0);
153 LCA_init();
154 m=read();
155 for(i=1;i<=m;++i)pos[i]=read();
156 LL l=1,r=smm;
157 while(l<=r){
158 LL mid=(l+r)>>1;
159 if(solve(mid)){
160 ans=mid;
161 r=mid-1;
162 }
163 else l=mid+1;
164 }
165 if(ans==1e11){printf("-1\n");}
166 else printf("%lld\n",ans);
167 return 0;
168 } 本文為部落客原創文章，轉載請注明出處。
![詳解STM32單片機的堆棧[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)