一个图论题, 需要一些性质, 需要足够的又不能超时的最短路信息来确保关键点的最小生成树不改变。

这个性质还是不是特别容易发现的啊。。

传送门

题目大意

\(n\)个点, \(m\)条边, 无向图, \(S\)个关键点, 多次询问, 问是否存在路径\(x \rightarrow y\), 使得相邻两个关键点的距离不超过\(b\)

(题目保证\(x\), \(y\)为关键点)。

解题报告

首先如果求出关键点之间两两的最短路, 那么题目就与非关键点没有什么关系了。

但是关键点的数量级是\(O(n)\)的, 所以非常的不支持。

考虑存在在最终的最小生成树上的关键点之间的路径具有什么性质。

如果\(a,b\)两点的最短路径中,存在点\(x\)到关键点\(c\)的距离小于到关键点\(a\)\(b\)的距离的任何一个, 那么\(a \rightarrow b\)的路径一定不在最终的最小生成树中。

因为\(a \rightarrow c \rightarrow b\)一定是比\(a \rightarrow b\)更好的策略。

所以需要的路径一定是“双色的”, 也就是一部分到\(x\)最近, 一部分到\(y\)最近。

那么枚举\(m\)条边, 如果两个点颜色不一样, 分别是\(a,b\), 那么就添加\(a \rightarrow b\)的最短路。

这些边足够组成最终的生成树。

所以就边权排序一波, 然后并查集维护一波。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(a);i<nn;++i)
const int N=200100;
struct edge {
int nx,to,v; edge(){}
edge(int nx,int to,int v)
:nx(nx),to(to),v(v){}
} e[N<<1];
struct ques {
int x,y,lm,t,id;
ques(int x=0,int y=0,int lm=0,int t=0,int id=0)
:x(x),y(y),lm(lm),t(t),id(id){}
bool operator <(const ques &b) const{ return lm==b.lm?t<b.t:lm<b.lm;}
} qy[N<<1];
struct side {
int x,y,d; side(){}
side(int x,int y,int d)
:x(x),y(y),d(d) {}
} sd[N];
int hd[N],tot,n,s,m,c[N],Q,ds[N],co[N],un,f[N];
bool vs[N],as[N]; queue<int> q;
inline void in(int &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
inline void add(int x,int y,int d) {
e[++tot]=edge(hd[x],y,d), hd[x]=tot;
e[++tot]=edge(hd[y],x,d), hd[y]=tot;
}
int find(int x) { if (f[x]!=x) f[x]=find(f[x]);return f[x]; }
inline void merge(int x,int y) {
int a=find(x),b=find(y); if (a!=b) f[a]=b;
}
int main() {
in(n),in(s),in(m); rep(i,1,s) in(c[i]);
int u,v,d; rep(i,1,m) {
in(u),in(v),in(d),sd[i]=side(u,v,d);
add(u,v,d), add(v,u,d);
}
rep(i,1,n) ds[i]=2000000001;
rep(i,1,s) ds[c[i]]=0,co[c[i]]=c[i],q.push(c[i]),vs[c[i]]=1;
while (!q.empty()) {
u=q.front(); q.pop(); vs[u]=0;
for (int i=hd[u];i;i=e[i].nx)
if (v=e[i].to, ds[u]+e[i].v<ds[v]) {
ds[v]=ds[u]+e[i].v, co[v]=co[u];
if (!vs[v]) vs[v]=1, q.push(v);
}
}
in(Q),un=Q; rep(i,1,n) f[i]=i;
rep(i,1,Q) in(u),in(v),in(d),qy[i]=ques(u,v,d,1,i);
rep(i,1,m) {
u=sd[i].x,v=sd[i].y;
if (co[u]!=co[v])
qy[++un]=ques(co[u],co[v],ds[u]+ds[v]+sd[i].d,0);
}
sort(qy+1,qy+1+un);
rep(i,1,un) {
if (qy[i].t) as[qy[i].id]=find(qy[i].x)==find(qy[i].y);
else merge(qy[i].x,qy[i].y);
}
rep(i,1,Q) puts((as[i])?"TAK":"NIE");
return 0;
}

留言