8
3
2015
0

【二分+贪心+LCA】NOIP2012 T6疫情控制

2013之前TG质量还是挺高的w

题目解释不清楚w你是懒吧啊喂! CodeVS传送门

考虑到每个军队一定是往根的方向走(能控制更多的城市),那么只需计算往上走的方式。

这么屌的题目一看就是二分答案(虽然我不知道怎么看出来的=w=)

转为判定性问题:时间为w,能否守住所有路。

LCA计算所有军队都往上走到的最远处(或是根),记录驻扎处(或是到根的军队以后剩下的可移动长度,按剩余长度排序*)。

dfs处理没能守住的、与顶点直接相邻的边,并按边长排序。

这时在根的军队有两个决策①挑一个边过去守②(无代价)退回上来的边。

这时*处排序就有用了:对于可移动长度最短的边,一定让它退回原边(因为它是最没用的),除非原边已守。将不能退的军队从小到大和剩余的没有守住的边用恰当方式守住(仿归并O(n)),发现守不住即可退出。

上面三行有一坨剪枝(如可移动军队与未守边的数量关系等),能AC就不赘述了。

近4K毒瘤丑Code:(三个DFS我也不知道我在想啥)

#include<cstdio>
#include<cstring>
#include<algorithm> 
#include<vector>
#define maxn 50010
#define maxm 100010
using namespace std;
struct Edge
{
	int from,to,w;
};
Edge es[maxm];
int first[maxn],next[maxm],n,m,a[maxn],b[maxn],Si=0,haha=0;
int v[maxn],vv[maxn];
void AddEdge(int from,int to,int w)
{
	Si++;
	es[Si]=(Edge){from,to,w};
	next[Si]=first[from];
	first[from]=Si;
}
int p[maxn][50];//以i跳2^j格的点
long long w[maxn][50];//跳的范围内
int S[maxn];
long long l=0,r=0,u;
int h[maxn];//每点深度= =
long long t1[maxn];
int dfs(int u)
{
	for (int i=first[u];i!=-1;i=next[i])
		if (!h[es[i].to])
		{
			Edge e=es[i];
			h[e.to]=h[u]+1;
			p[e.to][0]=u;
			w[e.to][0]=e.w;
			dfs(e.to);
		}
}

void init()
{
	for (int j=1;(1<<j)<=n;j++)
		for (int i=1;i<=n;i++)
			if (p[i][j-1]!=-1)
			{
				p[i][j]=p[p[i][j-1]][j-1];
				w[i][j]=w[i][j-1]+w[p[i][j-1]][j-1];
			}
}
long long LCA(int a,int b)
{
	int i,ans=0;
	if (h[a]<h[b]) swap(a,b);
	for (i=0;(1<<i)<=h[a];i++);
	i--;
	for (int j=i;j>=0;j--)
		if (h[a]-(1<<j)>=h[b])
		{
			ans+=w[a][j];
			a=p[a][j];
		}
	if (a==b) return ans;
	for (int j=i;j>=0;j--)
	{
		if (p[a][j]!=-1&&p[a][j]!=p[b][j])
		{
			ans+=w[a][j];
			a=p[a][j];
			ans+=w[b][j];
			b=p[b][j];
		}
	}
	return ans+w[a][0]+w[b][0];
}
int Swim(int a,long long ww)
{
	int i;
	for (i=0;(1<<i)<=h[a];i++);
	i--;
	for (int j=i;j>=0;j--)
	{
		if (ww-w[a][j]>=0) 
		{
			ww-=w[a][j];
			a=p[a][j];
		} 
	}
	return a;
}
int Dfs(int u,int f)
{
	S[u]=f;
	for (int i=first[u];i!=-1;i=next[i])
		if (!S[es[i].to])
			Dfs(es[i].to,f);
}
void read()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		first[i]=-1;
	for (int i=1;i<=n-1;i++)
	{
		long long u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		r+=w;
		AddEdge(u,v,w);
		AddEdge(v,u,w);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
		scanf("%d",&a[i]); 
	h[1]=1;
	dfs(1);
	init();
	S[1]=-1;
	for (int i=first[1];i!=-1;haha++,i=next[i])
	{
		Dfs(es[i].to,es[i].to);
	}
}
int DFS(int u)
{
	if (b[u]) return 1;
	v[u]=1;
	int w=1,x=0;
	for (int i=first[u];i!=-1;i=next[i])
		if (!v[es[i].to])
		{
			w&=DFS(es[i].to);
			if (!w) return 0;
			x=1;
		}
	if (x==0) return 0;
	return w;
}
int left1[maxn],left2[maxn];
int cmp1(int a,int b)
{
	return t1[a]>t1[b];
}
int cmp2(int a,int b)
{
	return es[a].w<es[b].w;
}
int check(long long w)
{
	memset(b,0,sizeof(b));
	memset(v,0,sizeof(v));
	memset(vv,0,sizeof(vv));
	int Siz1=0,Siz2=0;
	for (int i=1;i<=m;i++)
	{
		if (t1[a[i]]>w) b[Swim(a[i],w)]=1;
		else left1[++Siz1]=a[i];//w-t1[i]
	}
	v[1]=1;
	for (int i=first[1];i!=-1;i=next[i])
		if (!DFS(es[i].to)) left2[++Siz2]=i;//es[i].w
		else vv[es[i].to]=1;
	if (Siz1<Siz2) return 0;
	sort(left1+1,left1+1+Siz1,cmp1);
	sort(left2+1,left2+1+Siz2,cmp2);
	int j=1;
	for (int i=1;i<=Siz1;i++)
	{
		if (!vv[S[left1[i]]]) vv[S[left1[i]]]=1;
		else
		{
			while (j<=Siz2&&vv[es[left2[j]].to]) j++;
			while (i<=Siz1&&w-t1[left1[i]]<es[left2[j]].w) i++;
			if (j>Siz2) return 1;
			if (i>Siz1) return 0;
			vv[es[left2[j]].to]=1;
		}
	}
	while (j<=Siz2&&vv[es[left2[j]].to]) j++;
	if (j<=Siz2) return 0;
	return 1;
}
int main()
{
	freopen("BL.in","r",stdin);
	read();
	if (haha>m) 
	{
		printf("-1");
		return 0;
	}
	l=0;
	for (int i=1;i<=m;i++)
		t1[a[i]]=LCA(a[i],1);
	while (l<r)
	{
		u=l+r>>1;
		if (check(u)) r=u;
		else l=u+1;
	}
	long long ans;
	if (r==u) ans=u;
	if (l==u+1) ans=u+1;
	printf("%lld",ans);
	return 0;
}

 

Category: NOIP | Tags: 二分 贪心 LCA | Read Count: 338

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com