6301 疫情控制 0x60「图论」例题

描述

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例输入

样例输出

数据范围与约定

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

对于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。

来源

CCF NOIP2012 D2T3

        </article>

题解

参照evenbao的题解。

细心观察发现：此题的答案具有单调性，也就是说，如果p小时能控制疫情，那么q小时也能控制疫情(q > p),因此我们可以二分答案，这是此题的突破口

问题就转化为了检验”Mid小时是否可以控制住疫情“

我们发现，既然要求所有叶子节点得到管辖，那么，军队所在的节点深度越浅，所能管辖的节点数就越多，我们不妨让每支军队都先移动到所能移动的最顶端（不能移动到根节点），具体实现时，我们可以通过倍增预处理每个节点向上2^j条边的边权总和。

此时，我们可以将军队分为两类：

第一类：位于根节点的儿子节点

第二类：位于非根节点的儿子节点

对于第二类军队，我们让它保持不动即可，对于第一类军队，我们可以让它管辖自己所在子树的叶子节点，当然，我们也可以让它跨过根节点，管辖其所能到达的（不超过时间限制的），其它子树的叶子节点

这里有一条结论：对于一支第一类军队，如果这支军队不能跨过根节点并回到该节点，那么该节点必然由目前停留在这个节点上，且不能跨过根节点并回到该节点的，剩余时间最少的军队所管辖

根据这条结论，我们对于每个尚未被管辖的，根节点的子节点，查找是否有目前在该节点上并不能跨过根节点回到该节点的第一类军队，在这些军队中找剩余时间最少的管辖该节点，并将这支军队删除

对于剩余的第一类军队，我们可以先求出尚未被管辖的，根节点的子节点，然后，将军队按剩余时间 - 到达根节点的时间升序排列，将节点按到根节点的距离升序排列，贪心扫描一遍即可

时间复杂度\(O((n+m)\log n\log SUM)\)，SUM为边权和。

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;

    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

using namespace std;

co int N=5e4+1;

int head[N],Edge[N*2],Leng[N*2],Next[N*2],tot;

int n,m,t,a[N],b[N],g[N],fa[N][16],sh[N];

ll c[N],d[N],f[N],dis[N][16],sum;

vector<ll> arv[N];

queue<int> q;

bool v[N],w[N];

void add(int x,int y,int z){

	Edge[++tot]=y,Leng[tot]=z,Next[tot]=head[x],head[x]=tot;

}

void bfs(){

	v[1]=1;

	for(int i=head[1];i;i=Next[i]){

		int y=Edge[i];

		q.push(y);

		v[y]=1;

		b[sh[y]=++t]=i;

	}

	while(q.size()){

		int x=q.front();

		q.pop();

		for(int i=head[x];i;i=Next[i]){

			int y=Edge[i];

			if(v[y]) continue;

			q.push(y);

			v[y]=1;

			fa[y][0]=x;

			dis[y][0]=Leng[i];

			for(int j=1;j<16;++j){

				fa[y][j]=fa[fa[y][j-1]][j-1];

				dis[y][j]=dis[y][j-1]+dis[fa[y][j-1]][j-1];

			}

		}

	}

}

bool dfs(int x){ // check if ok

	v[x]=1;

	if(!sh[x]&&w[x]) return 1;

	bool flag=0; // not leaf

	for(int i=head[x];i;i=Next[i]){

		int y=Edge[i];

		if(v[y]) continue;

		flag=1;

		if(!dfs(Edge[i])) return 0;

	}

	return flag;

}

bool work(ll now){

	for(int i=1;i<=t;++i) arv[i].clear();

	memset(v,0,sizeof v),memset(w,0,sizeof w);

	v[1]=1;

	for(int i=1;i<=m;++i){

		g[i]=a[i],d[i]=0;

		for(int j=15;j>=0;--j)

			if(fa[g[i]][j]&&d[i]+dis[g[i]][j]<=now)

				d[i]+=dis[g[i]][j],g[i]=fa[g[i]][j];

		w[g[i]]=1;

		int j=sh[g[i]];

		if(j){

			arv[j].push_back(now-d[i]);

			if(arv[j].size()>1&&now-d[i]>arv[j][arv[j].size()-2])

				swap(arv[j][arv[j].size()-1],arv[j][arv[j].size()-2]);

		}

	}

	int p=0,q=0;

	for(int i=1;i<=t;++i){

		if(!dfs(Edge[b[i]])){

			if(arv[i].size()&&arv[i][arv[i].size()-1]<2*Leng[b[i]])

				arv[i].pop_back();

			else f[++q]=Leng[b[i]];

		}

		for(unsigned j=0;j<arv[i].size();++j)

			if(arv[i][j]>=Leng[b[i]])

				c[++p]=arv[i][j]-Leng[b[i]];

	}

	sort(c+1,c+p+1),sort(f+1,f+q+1);

	if(p<q) return 0;

	for(int i=q,j=p;i;--i,--j)

		if(c[j]<f[i]) return 0;

	return 1;

}

int main(){

	read(n);

	for(int i=1,x,y,z;i<n;++i){

		read(x),read(y),read(z);

		add(x,y,z),add(y,x,z),sum+=z;

	}

	read(m);

	for(int i=1;i<=m;++i) read(a[i]);

	bfs();

	ll l=0,r=sum+1;

	while(l<r){

		ll mid=(l+r)>>1;

		if(work(mid)) r=mid;

		else l=mid+1;

	}

	if(l>sum) puts("-1");

	else printf("%lld\n",l);

	return 0;

}

巴特西

CH6301 疫情控制