【洛谷P1084】疫情控制【二分+倍增+DFS+贪心】

题目链接

分析

我A紫题了耶

这题乍一看好像不难啊就一个树形DP啊最多加上LCA处理一下啊。。。想来想去不太行。

feelings：有一点是确定的，就是我们要让军队尽量离根节点近一点，这样子就可以让这个军队控制的节点更多。而答案就是用时最大的那个军队的时间，而我们要让这个最大值最小，所以可能是二分答案。

这题思路线比较长，从这两个点入手，大致分几个步骤，我一个一个写出。

1、倍增预处理关系和距离

“让军队向上移动”的“上提”操作，就很容易想到用倍增优化。
设 $f[i][j]$ 为 $i$ 往上 $2^j$ 个节点，容易知道 $f[i][0]$ 就是 $i$ 的父亲。设 $dis[i][j]$ 为 $i$ 到 $i$ 往上$2^j$ 个节点的距离。由类似求LCA前的预处理那样子，递推式显然，用个DFS遍历很容易求出。不会的先去学倍增LCA先。

void dfs(int x,int fx,int d)//倍增预处理 
{
	f[x][0]=fx;
	dis[x][0]=d;
	for(int i=1;i<=16;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];
	}
	for(int i=hd[x];i;i=e[i].next)
	{
		if(e[i].to!=fx) dfs(e[i].to,x,e[i].w);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2、二分答案

直接二分一个时间，作为本次每支军队移动的最大时间，判断行不行，然后再次二分。这一部分很简单。

    int l=1,r=1000000;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(pd(mid))
		{
			fff=1;//有解标记
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
1
2
3
4
5
6
7
8
9
10
11
12

3、“上提”操作，处理剩余路程

枚举每一个军队，让ta尽量往根节点跳，不能跳到根节点，这个跟LCA跳是一样的，同时记录跳的过程中花费的代价，如果最后是有能力跳到根节点的就记录成“剩余军队”，否则直接在原地驻守。对于所有能跳到根节点的军队，记录所有从根节点的儿子跳过来的军队中的最小值，后面有用。

    for(int i=1;i<=m;i++)
	{
		ll x=army[i],sum=0;
		for(int j=18;j>=0;j--)//倍增跳 
		{
			if(f[x][j]>1&&sum+dis[x][j]<=lim)
			{
				sum+=dis[x][j];
				x=f[x][j];
			}
		}
		if(f[x][0]==1&&lim-sum-dis[x][0]>=0)//如果能跳到根 
		{
			rest[++rest_num].s=lim-sum-dis[x][0];
			rest[rest_num].p=i;
			if(!resnum[x]||rest[rest_num].s<resmin[x])//记录最小 
			{
				resnum[x]=i;
				resmin[x]=rest[rest_num].s;
			}
		}
		else stationed[x]=1;//否则直接确定驻守 
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、查找“空隙”并记录

这个地方其实就是用DFS实现，如果该节点被封死，那就不用继续递归了，ta的子树也已经被封死。如果一个点是叶子并且没被驻守，直接返回0，如果不是根节点且自己没人驻守，那子树中只要有一条空隙（到达叶子结点的）就是不行的。我们只需要记录所有根的儿子当中哪个有空隙(emp结构体)，因为显然我们用剩余的军队去补空隙的时候只会去到根的子节点，才用时最小，再往下跑没意义。

int checktree(int x,int fa)//判断有没有空隙并记录空隙 
{
	int ff=1,leaf=1;
	if(stationed[x]) return 1;
	for(int i=hd[x];i;i=e[i].next)
	{
		if(e[i].to==fa) continue;
		leaf=0;//非叶子节点 
		if(!checktree(e[i].to,x))
		{
			ff=0;//有least一个空隙 
			if(x==1) 
			{
				emp[++emp_num].p=e[i].to;//只记录根的子节点哪个有空隙 
				emp[emp_num].s=e[i].w;
			}
			else return 0;
		}
	} 
	if(leaf&&!stationed[x]) return 0;
	else return ff;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5、贪心转移军队

我们将剩余军队按剩余时间从大到小排序(省枚举时间)，空隙当中到根的距离也按大到小排序。显然剩余多的军队应该尽量去补“空隙”权值大的地方。枚举空隙，匹配军队给他并记录用过了，优先选本身就在那棵子树上的最小的那个点看能不能到，如果不能就暴力枚举军队看看哪个可以，只要有一个空隙每个军队都没法不上，就判断不成功。

/*--------------贪心转移军队---------------*/
	sort(rest+1,rest+rest_num+1,cmp1);
	sort(emp+1,emp+emp_num+1,cmp2);
	v[0]=1;
	int now=1;
	for(int i=1;i<=emp_num;i++)
	{
		if(!v[resnum[emp[i].p]])
		{
			v[resnum[emp[i].p]]=1;
			continue;
		}
		while(now<=rest_num&&(v[rest[now].p]||rest[now].s<emp[i].s)) now++;//枚举军队
		if(now>rest_num) return 0;//都不行
		else v[rest[now].p]=1;
	}
	return 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上完整代码

很考验码力啊

#include
#include
#include
#include
using namespace std;
typedef long long ll;

struct node
{
	int to,next,w;
}e[100010];
struct donkey
{
	ll s;int p;
}rest[100010];
struct godcat
{
	ll s;int p;
}emp[100010];

int n,m,army[50010],fff;
int hd[100010],tot;
ll f[100010][20],dis[100010][20],ans; 
int resnum[50010],resmin[50010];
int stationed[50010],v[50010];
ll emp_num,rest_num;

void add(int x,int y,int w)
{
	e[++tot]=(node){y,hd[x],w};
	hd[x]=tot;
}

int cmp1(donkey l,donkey r)
{
	return l.s>r.s;
}
int cmp2(godcat l,godcat r)
{
	return l.s>r.s;
}

void dfs(int x,int fx,int d)//倍增预处理 
{
	f[x][0]=fx;
	dis[x][0]=d;
	for(int i=1;i<=16;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];
	}
	for(int i=hd[x];i;i=e[i].next)
	{
		if(e[i].to!=fx) dfs(e[i].to,x,e[i].w);
	}
}

int checktree(int x,int fa)//判断有没有空隙并记录空隙 
{
	int ff=1,leaf=1;
	if(stationed[x]) return 1;
	for(int i=hd[x];i;i=e[i].next)
	{
		if(e[i].to==fa) continue;
		leaf=0;//非叶子节点 
		if(!checktree(e[i].to,x))
		{
			ff=0;//有least一个空隙 
			if(x==1) 
			{
				emp[++emp_num].p=e[i].to;//只记录根的子节点哪个有空隙 
				emp[emp_num].s=e[i].w;
			}
			else return 0;
		}
	} 
	if(leaf&&!stationed[x]) return 0;
	else return ff;
}

int pd(int lim)
{
	rest_num=emp_num=0;
    memset(resnum,0,sizeof(resnum));
    memset(stationed,0,sizeof(stationed));
    memset(v,0,sizeof(v));
    
	for(int i=1;i<=m;i++)
	{
		ll x=army[i],sum=0;
		for(int j=18;j>=0;j--)//倍增跳 
		{
			if(f[x][j]>1&&sum+dis[x][j]<=lim)
			{
				sum+=dis[x][j];
				x=f[x][j];
			}
		}
		if(f[x][0]==1&&lim-sum-dis[x][0]>=0)//如果能跳到根 
		{
			rest[++rest_num].s=lim-sum-dis[x][0];
			rest[rest_num].p=i;
			if(!resnum[x]||rest[rest_num].s<resmin[x])//记录最小 
			{
				resnum[x]=i;
				resmin[x]=rest[rest_num].s;
			}
		}
		else stationed[x]=1;//否则直接确定驻守 
	}
	if(checktree(1,0)) return 1;//找空隙并记录 
	/*--------------贪心转移军队---------------*/
	sort(rest+1,rest+rest_num+1,cmp1);
	sort(emp+1,emp+emp_num+1,cmp2);
	v[0]=1;
	int now=1;
	for(int i=1;i<=emp_num;i++)
	{
		if(!v[resnum[emp[i].p]])
		{
			v[resnum[emp[i].p]]=1;
			continue;
		}
		while(now<=rest_num&&(v[rest[now].p]||rest[now].s<emp[i].s)) now++;
		if(now>rest_num) return 0;
		else v[rest[now].p]=1;
	}
	return 1;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		add(y,x,w);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&army[i]);
	}
	dfs(1,0,0);
	/*------二分答案------*/
	int l=1,r=1000000;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(pd(mid))
		{
			fff=1;
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if(fff) cout<<ans;
	else cout<<-1;
	return 0;
}
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163