2013年10月16日
noip2012 疫情控制
描述
H国有n个城市，这n个城市用n-1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。
H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
格式
输入格式
第一行一个整数n，表示城市个数。
接下来的n-1行，每行3个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市u到城市v有一条长为w的道路。数据保证输入的是一棵树，且根节点编号为1。
接下来一行一个整数m，表示军队个数。
接下来一行m个整数，每两个整数之间用一个空格隔开，分别表示这m个军队所驻扎的城市的编号。
输出格式
共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
数据范围
保证军队不会驻扎在首都。
对于20%的数据，2≤ n≤ 10；
对于40%的数据，2 ≤n≤50，0
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define INF 999999999999
8 #define LL long long
9 #define Max(x,y) if(xy.t;
19 }
20 LL n,m,T;
21 LL next[N*2],last[N*2],to[N*2];
22 LL w[N*2];
23 LL p[N],from[N],root[N];
24 LL dis[N],left[N];
25 bool use[N];
26 queue q;
27 inline void addedge(LL a,LL b,LL c){
28 next[++T]=last[a]; last[a]=T; to[T]=b ; w[T]=c;
29 next[++T]=last[b]; last[b]=T; to[T]=a ; w[T]=c;
30 }
31 void fail(){
32 LL Tot=0;
33 for(LL i=last[1];i;i=next[i]) ++Tot;
34 if(Tot>m) {
35 printf("-1");
36 exit(0);
37 }
38 }
39 LL pushup(LL now,LL f){
40 if(!next[last[now]]) {
41 if(left[now]>=0ll) use[now]=1 ;
42 return left[now] ;
43 }
44 use[now]=1;
45 for(LL i=last[now];i;i=next[i])
46 if(to[i]!=f){
47 Max(left[now],pushup(to[i],now)-w[i]);
48 if(!use[to[i]]) use[now]=0;
49 }
50 if(left[now]>=0) use[now]=1;
51 return left[now];
52 }
53 bool check(LL lim){
54 LL numa=0,numb=0;
55 memset(left,-1,sizeof left);
56 memset(use,0,sizeof use);
57 memset(from,0,sizeof from);
58 for(LL i=1;i<=m;i++)
59 if(dis[p[i]]>=lim)
60 left[p[i]]=lim;
61 else
62 army[++numa]=P(root[p[i]],lim-dis[p[i]]);
63 pushup(1,0);
64 for(LL i=last[1];i;i=next[i])
65 if(!use[to[i]])
66 edge[++numb]=P(to[i],w[i]);
67 if(numb>numa) return false; // 军队不够
68 sort(army+1,army+numa+1,cmp);
69 sort(edge+1,edge+numb+1,cmp);
70 //----来自该节点的所剩时间最少的军队----
71 for(LL i=numa;i;i--)
72 if(!from[army[i].p])
73 from[army[i].p]=i;
74 //--------------------------------------
75 LL la=1,lb=1;
76 memset(use,0,sizeof use);
77 use[0]=1;
78 while(lb<=numb&&la<=numa){
79 if(use[la]){
80 ++la;
81 continue ;
82 }
83 if(!use[from[edge[lb].p]]){
84 use[from[edge[lb].p]]=1;
85 ++lb;
86 continue ;
87 }
88 if(army[la].t
本文档为【NOIP试题集锦】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483