【Luogu1084】疫情控制

Source and Judge

NOIP2012 提高组 D2T3
Luogu1084
Caioj1556

Problem

【Brief description】

H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
【Input】

第一行一个整数 n,表示城市个数。

接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。

接下来一行一个整数 m,表示军队个数。

接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。
【Output】

共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
【Limited conditions】

保证军队不会驻扎在首都。

对于 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。
【Sample input】

4
1 2 1
1 3 2
3 4 3
2
2 2
【Sample output】

3
【Sample explanation】**

第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小时。

Record

5h

Analysis

请先思考后再展开

显然就是让时间最长的最小,然后可以考虑二分
然后,显然除了到根节点,其他时候深度越小越好,而且还是一棵树,那么就可以倍增搞一搞
而且,对于那些在时限内无法到达根节点的点,直接跑到最高处即可
于是,现在问题转化为:确定时限,判断【能到根节点而又余力的军队】和【没有接触瘟疫的根的子树】如何分配
(显然过了根节点,就没有必要往深处走了)

然后又是一波贪心2333,首先把军队和子树从小到大排序一下
情况①:同子树未覆盖,则优先覆盖(无条件),这样最节省资源
情况②:只能找其他子树下的空缺,有可能无任何贡献
这个方法的正确性是显而易见的,然鹅看到有人用奇奇怪怪的贪心也过去了……
可能有人看到这个“显而易见”又不爽?补充一下
对于一个a,如果本来是由b负责的,因为已经排好序,
如果b不是搞a,而是搞a后面的c,把a交给了b后面的d,则可行性不变,不会更优

最后提醒一下:
有一种错误的贪心(自己想错了……然后被自己卡了)
就是把有余力的军队,留最短的那支去管理自己的
但可能有一种情况:
三个点,然后一个很长,没人有空余,一个中间,有一个空余,一个很短,有两个空余
然后短的那部分,只能去中间长度的
按照现在的做法,会强行把中间那个留下,但其实放到长那地方,短的派一个过来会更优

正确的做法是,先把自己不能到根再回来的留下一个(这种情况,到别的更短地方不会更优)
那么剩下的就很好处理了,只要贪心的大管大即可
其中第一步很重要,避免原本能管理自己的,因为【空余减去到根距离】太小,导致浪费

这个贪心,万一在考场上太激动,没想到这个反例,然后分数被卡炸就惨了……

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=51000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
int hou[MAXN];
struct Edge
{
int y,g;
ll c;
}e[MAXN*2];
int ln=0;
void ins(int x,int y,ll c)
{
e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],c};hou[y]=ln;
}
//*******************预处理*******************
int f[MAXN][20];ll ds[MAXN][20];
void dfs(int x,int fa)
{
f[x][0]=fa;
for(int i=1;i<=16;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
ds[x][i]=ds[x][i-1]+ds[f[x][i-1]][i-1];
if(f[x][i]==0) break;
}
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
ds[y][0]=e[k].c;
dfs(y,x);
}
}
//*******************寻找*******************
bool fg[MAXN];
void dfs2(int x)
{
if(fg[x]) return;
bool son=0;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==f[x][0]) continue;
son=1;
dfs2(y);
if(!fg[y]) return;//空缺
}
if(son) fg[x]=1;
}
//*******************统计和分配*******************
int na,nb;
struct Nod//有余力的军队、空缺的【根节点下子树】
{
int id;//【根节点下子树】编号
ll rst;//长度
}sa[MAXN],sb[MAXN];
bool cmp(Nod a,Nod b) {return a.rst<b.rst;}
void presb()
{
for(int k=hou[1];k>0;k=e[k].g)
{
int y=e[k].y;
dfs2(y);
if(!fg[y]) sb[++nb]=(Nod){y,e[k].c};
}
}
//*******************验证*******************
int n,m;
int army[MAXN];
bool check(ll mid)
{
na=nb=0;
memset(fg,0,sizeof(fg));
for(int i=1;i<=m;i++)
{
int x=army[i];ll now=0;//已走长度
for(int j=16;j>=0;j--)
if(f[x][j]>1 and now+ds[x][j]<=mid)//非0且非根节点
now+=ds[x][j],x=f[x][j];
if(f[x][0]==1) sa[++na]=(Nod){x,mid-now-ds[x][0]};
else fg[x]=1;//debug
}
presb();
if(na<nb) return 0;
sort(sa+1,sa+na+1,cmp);
sort(sb+1,sb+nb+1,cmp);
int x=1;
for(int i=1;i<=na;i++)
{
if(!fg[sa[i].id]) fg[sa[i].id]=1;//优先同子树
else
{
if(sa[i].rst>=sb[x].rst) fg[sb[x++].id]=1;
else ;//无用
}
while(x<=nb and fg[sb[x].id]) x++;//准备
}
return x>nb;
}
//*******************主函数*******************
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,ll(c));
}
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&army[i]);
dfs(1,0);
ll l=0,r=ll(INF)*n,ans=-1;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf(BIGN,ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/32f8.html
转载请注明出处,谢谢!