[NOIP2015]运输计划

发布于 2017-10-16  131 次阅读



题目(vijos)
来说说这题怎么做吧
首先,最简单的,暴力枚举每条边,再跑路径,完毕。
:)
然后,考虑这是一棵树,路径唯一,所以可以用个树剖什么的。
:>
之后来到正解(95分)!
首先,求树上两点路径长度,不错的做法就是用LCA,求出(l,r)两点的lca,然后路径长度就是:
dis[l]+dis[r]-(dis[lca]<<1);
同时,用一个数组leng记录当前点与其父亲之间的边的权值。
然后有m个(l,r),所以lca必然是首选,并且将每个运输计划用结构体state保存(见代码)。
这道题最多只改变一条边的权值,并让最大值最小,怎么办?
妥妥的二分答案啊!
二分答案,check当前mid是否可行,
可以的话,ans=mid,R=mid-1,不行的话,L=mid+1
最后输出答案,完毕。


接下来考虑怎么check。
对于这很多个运输计划,很有可能会出现这种情况:

3->4这条边我们称之为“交边”。
可以看出,如果每次check都删除交边,可以使答案更优。
那么要求哪些运输计划的交边呢?这与mid有关。
只要当前运输计划的时间<=mid,那么就不管;
如果大于,那么就求树上每条边被这些大于mid的运输计划经过了多少次。
然后怎么求交边呢?运用到一个知识点:差分求交
用一个cnt记录一共有多少个运输计划大于mid,
用一个maxn表示哪个运输计划减去mid的花费时间最大,
这样,将其删掉后使解更优。
所以,return true的条件有两个:
1.c[i]==cnt
2.leng[i]>=maxn
否则return false。
另外,每次check都要初始化c为0。
完毕。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template  inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int L,R,mid;
int n,m;
struct edge{
	int vk;
	int wk;
	int nxt;
}e[600005];
int t,head[300005];
void ad(int u,int v,int w)
{
	e[++t].vk=v;
	e[t].wk=w;
	e[t].nxt=head[u];
	head[u]=t;
}
int dis[300005],p[300005][20];
int leng[300005];
int dep[300005];
int c[300005];
struct state{
	int l,r;
	int lca,len;
}a[300005];
void dfslca(int u)
{
	for (int i=1;i<=18;++i)
		p[u][i]=p[p[u][i-1]][i-1];
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		int w=e[i].wk;
		if (v==p[u][0]) continue;
		dis[v]=dis[u]+w;
		p[v][0]=u;
		dep[v]=dep[u]+1;
		leng[v]=w;
		dfslca(v);
	}
}
inline int lca(int x,int y)
{
	if (dep[x]>dep[y]) swap(x,y);
	for (int i=18;i>=0;--i)
	{
		if (dep[y]-(1<=0;--i)
	{
		if (p[x][i]==p[y][i]) continue;
		x=p[x][i],y=p[y][i];
	}
	return p[y][0];
}
void dfs(int u)
{
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==p[u][0]) continue;
		dfs(v);
		c[u]+=c[v];
	}
}
inline bool check()
{
	int maxn=0,cnt=0;
	memset(c,0,sizeof c);
	for (int i=1;i<=m;++i)
	{
		if (a[i].len>mid)
		{
			++cnt;
			++c[a[i].l],++c[a[i].r];
			c[a[i].lca]-=2;
			maxn=max(maxn,a[i].len-mid);
		}
	}
	dfs(1);
	for (int i=1;i<=n;++i)
		if (leng[i]>=maxn && c[i]==cnt)
			return true;
	return false;
}
int main()
{
	read(n),read(m);
	for (register int i=1;i<n;++i)
	{
		int x,y,z;
		read(x),read(y),read(z);
		ad(x,y,z),ad(y,x,z);
	}
	dfslca(1);
	for (register int i=1;i<=m;++i)
	{
		read(a[i].l),read(a[i].r);
		a[i].lca=lca(a[i].l,a[i].r);
		a[i].len=dis[a[i].l]+dis[a[i].r]-(dis[a[i].lca]<<1);
		R=max(R,a[i].len);
	}
	int ans=0;
	while (L<=R)
	{
		mid=(L+R)>>1;
		if (check()) ans=mid,R=mid-1;
		else L=mid+1;
	}
	printf(
	return 0;
}

为什么只有95分?
原因出在求LCA上。
这里的话用tarjan离线求LCA要比倍增快一些,
不过考虑的某些oj的评测机很棒,结果还是A了233
然而codevs就不会A掉,最后一个点始终TLE。
所以还是用tarjan离线求吧。