Test 7.12 T2

题目描述

有一张 n 个点 m 条边的无向图，其中有 s 个点上有加油站。有 Q 次询问(a,b,c)，问能否开一辆油箱容积为 c 的车从 a 走到 b。

输入格式

第一行三个整数 n,s,m。

接下来一行 s 个数，表示有加油站的节点。

接下来 m 行，每行三个整数 (x,y,z)，表示一条连接 x,y，权值为 z 的边。

接下来一行一个整数 Q。

接下来 Q 行，每行三个整数 (a,b,c)，表示询问。

输出格式

共 Q 行，若对应询问可行，输出 TAK，否则输出 NIE。

样例输入

样例输出

TAK

TAK

TAK

NIE

数据范围

Part 1：2 个测试点，每个 5 分：\(n,Q\leq100\)

Part 2：1 个测试点，20 分：\(n\leq1000\)

Part 3：2 个测试点，每个 10 分：\(n=s\)

Part 4：10 个测试点，每个 5 分：无特殊性质

对于所有数据，\(2\leq s\leq n\leq200000,1\leq m\leq 200000,z\leq10000,c\leq2*10^9\)

解析

如果从一个加油站能够到达另一个加油站，那么说明这条路径是可行的。所以，对于每一个(a,b)，我们需要知道(a,b)之间权值最大的边是否小于c。很自然的可以想到最大生成树，但问题的关键在于如何建出最大生成树。

对于这棵生成树，我们可以只保留加油站节点。为了减少边的规模，设原图中到每个点最近的加油站节点为pos[i]，那么如果一条边的两个端点的pos值不相同，则对应的两个加油站之间必然需要连一条边，边权为

\[dis(pos[u],u)+w(u,v)+dis(pos[v],v)
\]

具体的pos值可以用多源点最短路径去求。设每个加油站都是一个起点，pos为自身，那么在转移过程中对于每一个\(dis[y]>dis[x]+w(x,y)\)，都有\(pos[y]=pos[x]\)。

在实现过程中，用离线操作会更加方便。将询问按c从小到大排序，每到一个询问都将边权小于当前c的树边的两端连起来，如果询问的a和b在同一个连通块中就说明可行。并查集维护连通性即可。

代码

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define N 200002

using namespace std;

struct node{

	int u,v,w;

}a[N];

struct query{

	int a,b,c,id;

}b[N];

int head[N],ver[N*2],nxt[N*2],edge[N*2],l;

int n,m,s,q,i,j=1,p,pos[N],dis[N],u[N],v[N],w[N],fa[N],num,ans[N];

bool in[N],e[N];

void insert(int x,int y,int z)

{

	l++;

	ver[l]=y;

	edge[l]=z;

	nxt[l]=head[x];

	head[x]=l;

}

void SPFA()

{

	queue<int> q;

	memset(dis,0x3f,sizeof(dis));

	memset(in,0,sizeof(in));

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

		if(e[i]){

			q.push(i);

			pos[i]=i;

			dis[i]=0;in[i]=1;

		}

	}

	while(!q.empty()){

		int x=q.front();

		q.pop();

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

			int y=ver[i];

			if(dis[y]>dis[x]+edge[i]){

				pos[y]=pos[x];

				dis[y]=dis[x]+edge[i];

				if(!in[y]){

					q.push(y);

					in[y]=1;

				}

			}

		}

		in[x]=0;

	}

}

int cmp1(const node &x,const node &y)

{

	return x.w<y.w;

}

int cmp2(const query &x,const query &y)

{

	return x.c<y.c;

}

int find(int x)

{

	if(fa[x]!=x) fa[x]=find(fa[x]);

	return fa[x];

}

int main()

{

	freopen("B.in","r",stdin);

	freopen("B.out","w",stdout);

	cin>>n>>s>>m;

	for(i=1;i<=s;i++){

		int x;

		cin>>x;

		e[x]=1;

		if(p==0) p=x;

	}

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

		cin>>u[i]>>v[i]>>w[i];

		insert(u[i],v[i],w[i]);

		insert(v[i],u[i],w[i]);

	}

	SPFA();

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

		if(pos[u[i]]!=pos[v[i]]) a[++num]=(node){pos[u[i]],pos[v[i]],dis[u[i]]+dis[v[i]]+w[i]};

	}

	cin>>q;

	for(i=1;i<=q;i++){

		cin>>b[i].a>>b[i].b>>b[i].c;

		b[i].id=i;

	}

	sort(a+1,a+num+1,cmp1);

	sort(b+1,b+q+1,cmp2);

	for(i=1;i<=n;i++) fa[i]=i;

	for(i=1;i<=q;i++){

		while(a[j].w<=b[i].c&&j<=num){

			fa[find(a[j].u)]=find(a[j].v);

			j++;

		}

		if(find(b[i].a)==find(b[i].b)) ans[b[i].id]=1;

	}

	for(i=1;i<=q;i++){

		if(ans[i]==1) cout<<"TAK"<<endl;

		else cout<<"NIE"<<endl;

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西