「BZOJ3700」「FJ2014集训」发展城市

2015年4月26日5,0903

Description

众所周知，Hzwer学长是一名高富帅，他打算投入巨资发展一些小城市。
Hzwer打算在城市中开N个宾馆，由于Hzwer非常壕，所以宾馆必须建在空中，但是这样就必须建立宾馆之间的连接通道。机智的Hzwer在宾馆中修建了N-1条隧道，也就是说，宾馆和隧道形成了一个树形结构。
Hzwer有时候会花一天时间去视察某个城市，当来到一个城市之后，Hzwer会分析这些宾馆的顾客情况。对于每个顾客，Hzwer用三个数值描述他：（S， T， V）表示该顾客这天想要从宾馆S走到宾馆T，他的速度是V。
Hzwer需要做一些收集一些数据，这样他就可以规划他接下来的投资。
其中有一项数据就是收集所有顾客可能的碰面次数。
每天清晨，顾客同时从S出发以V的速度前往T（注意S可能等于T），当到达了宾馆T的时候，顾客显然要找个房间住下，那么别的顾客再经过这里就不会碰面了。特别的，两个顾客同时到达一个宾馆是可以碰面的。同样，两个顾客同时从某宾馆出发也会碰面。

Input

第一行一个正整数T(1<=T<=20)，表示Hzwer发展了T个城市，并且在这T个城市分别视察一次。
对于每个T，第一行有一个正整数N(1<=N<=10^5)表示Hzwer在这个城市开了N个宾馆。
接下来N-1行，每行三个整数X，Y，Z表示宾馆X和宾馆Y之间有一条长度为Z的隧道
再接下来一行M表示这天顾客的数量。
紧跟着M行每行三个整数（S， T， V）表示该顾客会从宾馆S走到宾馆T，速度为v

Output

对于每个T，输出一行，表示顾客的碰面次数。

Sample Input

1
3
1 2 1
2 3 1
3
1 3 2
3 1 1
1 2 3
1
0

Sample Output

2
0

HINT

「数据规模」
1<=T<=20 1<=N<=10^5 0<=M<=10^3 1<=V<=10^6 1<=Z<=10^3

题解

虽然题面如此黑。。但是毕竟是Mektpoy神出的题，还是把坑填了

能在bzoj留几个名倍感荣幸。。。

搬运题解：

首先求出这颗树的欧拉序列，方便做LCA

因为顾客是10^3级别完全可以枚举两个顾客

那么剩下的问题就是在很短的时间内判断两个顾客是否会相遇

对于两个顾客设他们的路径是a→b c→d 我们先找到他们的路径中相同的部分

路径中相同的部分可能是一个点，也可能是很多个点组成的一条路径甚至是没有相同的部分。

那么从点入手，假设路径有相同的部分那么很显然 c到路径[a,b]最近的点一定在那个相同部分上面。

证明很显然。因为有重合的部分，那么这个点p必定在[c,d]路径上且是开始重合的第一个点。

那么我们只要找到c距离[a,b]最近的点u，和d距离[a,b]最近的点v

那么我们就找到了路径[u,v]是重合部分

如果没有重合部分呢?

令r=LCA(c,d)若u不在r的子树中即LCA(r,u)!=r那么就没有重合部分了。

那现在遗留了一个问题：这个最近的点怎么求呢?

我们以c为例：

此时令r=LCA(a,b)，假设c不在r的子树中，即LCA(c,r)!=r那么r就是我们要找的这个点

如果LCA(c,r)==r有三种情况：

第一种是LCA(a,c)==LCA(b,c)==r此时依然是r

另一种是LCA(a,c)!=r 那么此时就是LCA(a,c)

还有一种 LCA(b,c)!=r 此时是LCA(b,c)

这个画个图就能理解。。

事实上不用再分三类，因为如果LCA(a,c)!=r 那么这个点就一定是LCA(b,c)了。

最后剩下一个问题即是知道了相同路径如何判断是否相遇?（如果没有相同路径肯定不相遇）

那就分情况讨论了，比如说顾客方向相反啦，相同的时候怎么样怎么样啦。。

总之两个顾客到这个相同路径的起始时间和终止时间是确定的这个是可以O(1)求的//LCA是O(1)

所以虽然我们分了这么一堆情况最后处理两个顾客仍然是O(1)的

最后时间复杂度O(nlogn+m^2)

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int T,n,m,cnt,dfn,res;
int s[1005],t[1005],V[1005];
int Log[200005],last[100005],deep[100005],pos[100005];
int mn[18][200005],ans[18][200005];
ll d[100005];
struct edge{
	int to,next,v;
}e[200005];
void insert(int u,int v,int w)
{
	e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
	e[++cnt]=(edge){u,last[v],w};last[v]=cnt;
}
void dfs(int x,int fa)
{
	ans[0][++dfn]=x;
	mn[0][dfn]=deep[x];
	pos[x]=dfn;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			d[e[i].to]=d[x]+e[i].v;
			deep[e[i].to]=deep[x]+1;
			dfs(e[i].to,x);
			ans[0][++dfn]=x;
			mn[0][dfn]=deep[x];
		}
}
int lca(int x,int y)
{
	x=pos[x];y=pos[y];
	if(x>y)swap(x,y);
	int t=Log[y-x+1];
	return mn[t][x]<mn[t][y-bin[t]+1]?ans[t][x]:ans[t][y-bin[t]+1];
}
ll dis(int x,int y)
{
	return d[x]+d[y]-2*d[lca(x,y)];
}
int clo(int a,int b,int c)
{
	int r=lca(a,b),f1,f2;
	if(lca(r,c)!=r)return r;
	f1=lca(a,c);if(f1!=r)return f1;
    f2=lca(b,c);if(f2!=r)return f2;
	return r;
}
pair<int,int> getpath(int a,int b,int c,int d)
{
	int t1=clo(a,b,c),t2=clo(a,b,d),t3=clo(c,d,a),t4=clo(c,d,b);
	if(t1>t2)swap(t1,t2);
    if(t3>t4)swap(t3,t4);
	if(t1!=t3||t2!=t4)return make_pair(0,0);
	return make_pair(t1,t2);
}
bool solve(int x,int y)
{
	if(s[x]==s[y])return 1;
	pair<int,int> p=getpath(s[x],t[x],s[y],t[y]);
	int u=p.first,v=p.second;
	if(!u)return 0;
	if(u==v)
		return dis(s[x],u)*V[y]==dis(s[y],u)*V[x];
	else 
	{
		if(v==clo(u,v,s[x]))swap(u,v);
		if(clo(u,v,s[x])==clo(u,v,s[y]))
		{		
            ll d1=dis(s[x],u)*V[y],d2=dis(s[y],u)*V[x];
			if(d1>d2)swap(x,y);
			else if(d1==d2)return 1;
			return dis(s[x],v)*V[y]>=dis(s[y],v)*V[x];
		}
		else return (dis(s[x],u)*V[y]<=dis(u,s[y])*V[x]&&dis(s[y],v)*V[x]<=dis(v,s[x])*V[y]);
	}
}
int main()
{
	Log[0]=-1;for(int i=1;i<200000;i++)Log[i]=Log[i>>1]+1;
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	T=read();
	while(T--)
	{
		memset(last,0,sizeof(last));
		cnt=dfn=res=0;
		n=read();
		for(int i=1;i<n;i++)
		{
			int u=read(),v=read(),w=read();
			insert(u,v,w);
		}
		dfs(1,0);
		for(int i=1;i<=17;i++)
			for(int j=1;j<=dfn;j++)
				if(j+bin[i]-1<=dfn)
				{
					mn[i][j]=mn[i-1][j];
					ans[i][j]=ans[i-1][j];
					if(mn[i-1][j+bin[i-1]]<mn[i][j])
					{
						mn[i][j]=mn[i-1][j+bin[i-1]];
						ans[i][j]=ans[i-1][j+bin[i-1]];
					}
				}
		m=read();
		for(int i=1;i<=m;i++)
			s[i]=read(),t[i]=read(),V[i]=read();
		for(int i=1;i<=m;i++)
			for(int j=i+1;j<=m;j++)
				res+=solve(i,j);
		printf("%d\n",res);
	}
	return 0;
}

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

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int T,n,m,cnt,dfn,res;

int s[1005],t[1005],V[1005];

int Log[200005],last[100005],deep[100005],pos[100005];

int mn[18][200005],ans[18][200005];

ll d[100005];

struct edge{

int to,next,v;

}e[200005];

void insert(int u,int v,int w)

{

e[++cnt]=(edge){v,last[u],w};last[u]=cnt;

e[++cnt]=(edge){u,last[v],w};last[v]=cnt;

}

void dfs(int x,int fa)

{

ans[0][++dfn]=x;

mn[0][dfn]=deep[x];

pos[x]=dfn;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

{

d[e[i].to]=d[x]+e[i].v;

deep[e[i].to]=deep[x]+1;

dfs(e[i].to,x);

ans[0][++dfn]=x;

mn[0][dfn]=deep[x];

}

int lca(int x,int y)

{

x=pos[x];y=pos[y];

if(x>y)swap(x,y);

int t=Log[y-x+1];

return mn[t][x]<mn[t][y-bin[t]+1]?ans[t][x]:ans[t][y-bin[t]+1];

}

ll dis(int x,int y)

{

return d[x]+d[y]-2*d[lca(x,y)];

}

int clo(int a,int b,int c)

{

int r=lca(a,b),f1,f2;

if(lca(r,c)!=r)return r;

f1=lca(a,c);if(f1!=r)return f1;

f2=lca(b,c);if(f2!=r)return f2;

return r;

}

pair<int,int> getpath(int a,int b,int c,int d)

{

int t1=clo(a,b,c),t2=clo(a,b,d),t3=clo(c,d,a),t4=clo(c,d,b);

if(t1>t2)swap(t1,t2);

if(t3>t4)swap(t3,t4);

if(t1!=t3||t2!=t4)return make_pair(0,0);

return make_pair(t1,t2);

}

bool solve(int x,int y)

{

if(s[x]==s[y])return 1;

pair<int,int> p=getpath(s[x],t[x],s[y],t[y]);

int u=p.first,v=p.second;

if(!u)return 0;

if(u==v)

return dis(s[x],u)*V[y]==dis(s[y],u)*V[x];

else

{

if(v==clo(u,v,s[x]))swap(u,v);

if(clo(u,v,s[x])==clo(u,v,s[y]))

{

ll d1=dis(s[x],u)*V[y],d2=dis(s[y],u)*V[x];

if(d1>d2)swap(x,y);

else if(d1==d2)return 1;

return dis(s[x],v)*V[y]>=dis(s[y],v)*V[x];

}

else return (dis(s[x],u)*V[y]<=dis(u,s[y])*V[x]&&dis(s[y],v)*V[x]<=dis(v,s[x])*V[y]);

}

int main()

{

Log[0]=-1;for(int i=1;i<200000;i++)Log[i]=Log[i>>1]+1;

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

T=read();

while(T--)

{

memset(last,0,sizeof(last));

cnt=dfn=res=0;

n=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

dfs(1,0);

for(int i=1;i<=17;i++)

for(int j=1;j<=dfn;j++)

if(j+bin[i]-1<=dfn)

{

mn[i][j]=mn[i-1][j];

ans[i][j]=ans[i-1][j];

if(mn[i-1][j+bin[i-1]]<mn[i][j])

{

mn[i][j]=mn[i-1][j+bin[i-1]];

ans[i][j]=ans[i-1][j+bin[i-1]];

}

m=read();

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

s[i]=read(),t[i]=read(),V[i]=read();

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

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

res+=solve(i,j);

printf("%d\n",res);

}

return 0;

}

« 「BZOJ1095」[ZJOI2007] Hide 捉迷藏

LV24twx

为啥在bzoj会挂

oier

“如果没有重合部分呢?

令r=LCA(c,d)若u不在r的子树中即LCA(r,u)!=r那么就没有重合部分了。”

这里是不是有问题？
如果(a,b) 与（c,d）在同一条链上且不重合怎么办？就像 1——2——3——4，且这一条链同属于同一根节点
若1到4深度递增，令c=1，d=2，a=3，b=4,岂不是错了？

hzwer的小学弟

学长高富帅 orz

hzwer.com _ Home | http://hzwer.com

「BZOJ3700」「FJ2014集训」发展城市

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论