Luogu P2680 运输计划

题目描述

公元20442044 年，人类进入了宇宙纪元。

L 国有 nn 个星球，还有 n-1n−1 条双向航道，每条航道建立在两个星球之间，这 n-1n−1 条航道连通了 LL 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_iui 号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 jj，任意飞船驶过它所花费的时间为 t_jtj，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， LL 国国王同意小 PP 的物流公司参与 LL 国的航道建设，即允许小PP 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 mm 个运输计划。在虫洞建设完成后，这 mm 个运输计划会同时开始，所有飞船一起出发。当这 mm 个运输计划都完成时，小 PP 的物流公司的阶段性工作就完成了。

如果小 PP 可以自由选择将哪一条航道改造成虫洞，试求出小 PP 的物流公司完成阶段性工作所需要的最短时间是多少？

输入输出格式

输入格式：

第一行包括两个正整数 n, mn,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 11 到 nn 编号。

接下来 n-1n−1 行描述航道的建设情况，其中第 ii 行包含三个整数 a_i, b_iai,bi 和 t_iti，表示第 ii 条双向航道修建在 a_iai 与 b_ibi两个星球之间，任意飞船驶过它所花费的时间为 t_iti。数据保证 1 \leq a_i,b_i \leq n1≤ai,bi≤n 且 0 \leq t_i \leq 10000≤ti≤1000。

接下来 mm 行描述运输计划的情况，其中第 jj 行包含两个正整数 u_juj 和 v_jvj，表示第 jj 个运输计划是从 u_juj 号星球飞往 v_jvj号星球。数据保证 1 \leq u_i,v_i \leq n1≤ui,vi≤n

输出格式：

一个整数，表示小 PP 的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

所有测试数据的范围和特点如下表所示

Luogu P2680 运输计划

请注意常数因子带来的程序效率上的影响。

第一步：由于最短，所以想到二分答案

第二步：已知答案，找到所以比答案大的方案，改造成虫洞的边一定在这些方案的交上

第三步：用差分思想求出交，并取出最大的边，把最大的方案减去最大的边，看是否小于等于答案

GG啦

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
inline int read()
{
	int ret=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9')
		ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
	return ret;
}

int n,m,cnt,l,r,ans,anss,lca;
const int N=6e5+5;
int to[N],nxt[N],w[N],he[N],dep[N],a[N],tree[N];
int f[N][20],fw[N][20],lg[N];

inline void add(int u,int v,int k)
{
	to[++cnt]=v;
	nxt[cnt]=he[u];
	w[cnt]=k;
	he[u]=cnt;
}

void dfs(int fa,int u)
{
	dep[u]=(!fa)?0:dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=lg[dep[u]];i++)
		f[u][i]=f[f[u][i-1]][i-1],
		fw[u][i]=fw[u][i-1]+fw[f[u][i-1]][i-1];
		
	for(int e=he[u];e;e=nxt[e])
	{
		int v=to[e];
		if(v!=fa)
			fw[v][0]=w[e],
			dfs(u,v);
	}
}

void dfs1(int fa,int u,int s)
{
	tree[u]=a[u];
	for(int e=he[u];e;e=nxt[e])
	{
		int v=to[e];
		if(v!=fa)
			dfs1(u,v,w[e]),tree[u]+=tree[v];
	}
	if(tree[u]==cnt) anss=max(anss,s);
}

int LCA(int u,int v)
{
	if(dep[u]>dep[v]) swap(u,v);
	int ret=0;
	while(dep[u]<dep[v])
		ret+=fw[v][lg[dep[v]-dep[u]]],
		v=f[v][lg[dep[v]-dep[u]]];
		
	for(int i=lg[dep[u]];i>=0;i--)
		if(f[u][i]!=f[v][i])
			ret+=fw[v][i]+fw[u][i],
			u=f[u][i],v=f[v][i];
	if(u!=v)
		ret+=fw[u][0]+fw[v][0],u=f[u][0];
	lca=u;
	return ret;
}
struct NA{
	int l,r,t,lca;
}e[N];

bool cmp(NA i,NA j)
{
	return i.t>j.t;
}

int main()
{
	n=read(),m=read();
	cnt=0;
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),k=read();
		add(u,v,k),add(v,u,k);
	}
	lg[0]=-1;
	for(int i=1;i<=n;i++) 
		lg[i]=lg[i>>1]+1;
	cnt=0;
	dfs(0,1);
	for(int i=1;i<=m;i++)
		lca=0,
		e[i].l=read(),e[i].r=read(),
		e[i].t=LCA(e[i].l,e[i].r),r=max(r,e[i].t),e[i].lca=lca;
	sort(e+1,e+m+1,cmp);
	
	l=0; ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		cnt=0;anss=0; 
		for(int i=0;i<=n;i++) a[i]=0;
		while(e[++cnt].t>mid)
			a[e[cnt].l]++,a[e[cnt].r]++,
			a[e[cnt].lca]-=2;
		if(e[cnt].t<=mid) cnt--;
		dfs1(0,1,0);
		if(e[1].t-anss>mid) l=mid+1;
				else ans=mid,r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

Luogu P2680 运输计划

题目描述

输入输出格式

输入输出样例

说明

相关推荐