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。

样例输入

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)，我们需要知道(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;
}

Test 7.12 T2

原文：https://www.cnblogs.com/LSlzf/p/11178576.html