题解 [BZOJ4144] Petrol

偏执的太偏执、 2021-09-30 07:48 270阅读 0赞

### 题目描述 ###

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

### 输入格式 ###

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

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

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

接下来一行一个整数 Q。

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

### 输出格式 ###

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

### 样例输入 ###

6 4 5  
1 5 2 6  
1 3 1  
2 3 2  
3 4 3  
4 5 5  
6 4 5  
4  
1 2 4  
2 6 9  
1 5 9  
6 5 8

### 样例输出 ###

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\\)两地的路径分成若干段加油站到加油站的路径,

如果最大值小于等于容量\\(C\\)就能到达.

那么,我们就可以把加油站拿出来建一个最小生成树,

然而,怎么建啊?

暴力两两连边?

然后就\\(TLE+MLE\\)了...

其实,我们可以先求出离每个点\\(i\\)最近的加油站\\(w\[i\]\\)和距离\\(d\[j\]\\),

然后对于原图中的每条边\\(x\\),\\(y\\),

如果\\(w\[x\]!=w\[y\]\\),就把\\(w\[x\],w\[y\]\\)连一条边,

距离就是\\(d\[x\]+d\[y\]+w\_\{x,y\}\\).

而\\(w\[i\],d\[i\]\\)怎么求呢?

跑多源SPFA就行啦.

然而到这里就完了吗?

其实我们还可以让代码更简单一些.

因为只需要判断连通性,

所以我们可以先将询问按容量排序,

再一边加边,用并查集维护连通块就行了.

code:

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout) using namespace std; inline int read(){ int sum=0,f=1;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return f*sum; } const int N=400001; struct edge{int to,next,w;}e[N<<1]; struct ques{int x,y,w,id;}q[N],E[N<<1],A[N<<1]; int n,s,m,Q,a[N],isoil[N],dep[N]; int head[N],cnt=0,Head[N],Cnt=0; int w[N],d[N],v[N],ans[N]; int da[N],f[N][21],fa[N][21]; queue <int> que; bool cmp(ques a,ques b){return a.w<b.w;} inline void add(int x,int y,int w){ e[++cnt]=(edge){head[x],y,w};head[x]=cnt; } inline void spfa(){ memset(d,0x3f,sizeof(d)); for(int i=1;i<=s;i++) que.push(a[i]),d[a[i]]=0,w[a[i]]=a[i],v[a[i]]=1; while(!que.empty()){ int x=que.front();que.pop(); for(int i=head[x];i;i=e[i].to){ int k=e[i].next; if(d[k]<=d[x]+e[i].w) continue; d[k]=d[x]+e[i].w;w[k]=w[x]; if(!v[k]) v[k]=1,que.push(k); } v[x]=0; } } inline int find_fa(int x){return x==da[x]? x:da[x]=find_fa(da[x]);} inline void link(int i){ int a=find_fa(E[i].x),b=find_fa(E[i].y); if(a!=b) da[a]=b; } int main(){ n=read();s=read();m=read(); for(int i=1;i<=s;i++) a[i]=read(),isoil[a[i]]=1; for(int i=1;i<=n;i++) da[i]=i; for(int i=1;i<=m;i++){ A[i].x=read();A[i].y=read();A[i].w=read(); add(A[i].x,A[i].y,A[i].w);add(A[i].y,A[i].x,A[i].w); } spfa(); for(int i=1;i<=m;i++){ int x=A[i].x,y=A[i].y; if(w[x]!=w[y]) E[++Cnt]=(ques){w[x],w[y],d[x]+d[y]+A[i].w}; } Q=read();int tot=1; for(int i=1;i<=Q;i++) q[i].x=read(),q[i].y=read(),q[i].w=read(); for(int i=1;i<=Q;i++) q[i].id=i; sort(q+1,q+Q+1,cmp);sort(E+1,E+Cnt+1,cmp); for(int i=1;i<=Q;i++){ while(E[tot].w<=q[i].w&&tot<=Cnt) link(tot++); int a=find_fa(q[i].x),b=find_fa(q[i].y); if(a==b) ans[q[i].id]=1; } for(int i=1;i<=Q;i++) puts(ans[i]? "TAK":"NIE"); return 0; }

转载于:https://www.cnblogs.com/zsq259/p/11178531.html