BZOJ 4144: [AMPPZ2014]Petrol

时间：2021-06-19 16:30:45

4144: [AMPPZ2014]Petrol

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 457  Solved: 170
[Submit][Status][Discuss]

Description

给定一个n个点、m条边的带权无向图，其中有s个点是加油站。
每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。
q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。
 

Input

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。
第二行包含s个互不相同的正整数c[1],c[2],...c[s](1<=c[i]<=n)，表示每个加油站。
接下来m行，每行三个正整数u[i],v[i],d[i](1<=u[i],v[i]<=n,u[i]!=v[i],1<=d[i]<=10000)，表示u[i]和v[i]之间有一条长度为d[i]的双向边。
接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。
接下来q行，每行包含三个正整数x[i],y[i],b[i](1<=x[i],y[i]<=n,x[i]!=y[i],1<=b[i]<=2*10^9)，表示一个询问。
 

Output

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。
 

Sample Input

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

Sample Output

TAK
TAK
TAK
NIE

HINT

 

Source

[Submit][Status][Discuss]

分析

为了回答每个询问，我们需要加油站之间的最小生成树。

求最小生成树的方式是：让所有的加油站dis为0，做多源最短路，同时记录距离每个点最近的加油站。然后枚举边，可以得到两个加油站之间的可能最短距离。做Kruskal或Prim即可。

求到最小生成树之后，用倍增法维护路径上的最大权值即可。

代码

 #include <cmath>

 #include <queue>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define N 500005

 #define inf 0x3f3f3f3f

 int n, m, s, c[N];

 struct edge

 {

     int x, y, w;

     edge(void) {};

     edge(int _x, int _y, int _w) :

         x(_x), y(_y), w(_w) {};

     friend bool operator < (const edge &a, const edge &b)

     {

         return a.w < b.w;

     }

 };

 struct step

 {

     int id, dis;

     step(void) {};

     step(int a, int b) :

         id(a), dis(b) {};

     friend bool operator < (const step &a, const step &b)

     {

         return a.dis > b.dis;

     }

 };

 namespace kirito

 {

     edge e[N]; int edge_cnt = ;

     int hd[N], to[N], vl[N], nt[N], tot;

     void addEdge(int x, int y, int w)

     {

         nt[tot] = hd[x]; to[tot] = y; vl[tot] = w; hd[x] = tot++;

         nt[tot] = hd[y]; to[tot] = x; vl[tot] = w; hd[y] = tot++;

     }

     int dis[N], from[N]; 

     priority_queue<step> pq;

 }

 namespace masiro

 {

     edge e[N]; int edge_cnt = ;

     void pushEdge(int x, int y, int w)

     {

         e[++edge_cnt] = edge(x, y, w);

     }

     int hd[N], to[N], vl[N], nt[N], tot;

     void addEdge(int x, int y, int w)

     {

         nt[tot] = hd[x]; to[tot] = y; vl[tot] = w; hd[x] = tot++;

         nt[tot] = hd[y]; to[tot] = x; vl[tot] = w; hd[y] = tot++;

     }

     int fa[N];

     int find(int u)

     {

         return fa[u] == u ? u : fa[u] = find(fa[u]);

     }

     int root;

     int dep[N], fat[N][], mex[N][];

     void predfs(int u, int f)

     {

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

         {

             fat[u][i] = fat[fat[u][i - ]][i - ];

             mex[u][i] = max(mex[u][i - ], mex[fat[u][i - ]][i - ]);

         }

         for (int i = hd[u]; ~i; i = nt[i])

             if (to[i] != f)

             {

                 dep[to[i]] = dep[u] + ;

                 mex[to[i]][] = vl[i];

                 fat[to[i]][] = u;

                 predfs(to[i], u);

             }

     }

 }

 void prework1(void)

 {

     using namespace kirito;

     memset(dis, inf, sizeof(dis)); 

     for (int i = ; i <= s; ++i)

     {

         dis[c[i]] = ;

         from[c[i]] = c[i];

         pq.push(step(c[i], ));

     }

     while (!pq.empty())

     {

         step top = pq.top(); pq.pop();

         if (dis[top.id] != top.dis)

             continue;

         for (int i = hd[top.id]; ~i; i = nt[i])

             if (dis[to[i]] > vl[i] + top.dis)

             {

                 from[to[i]] = from[top.id];

                 dis[to[i]] = vl[i] + top.dis;

                 pq.push(step(to[i], dis[to[i]]));

             }

     }

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

         if (from[e[i].x] ^ from[e[i].y])

             masiro::pushEdge(from[e[i].x], from[e[i].y], dis[e[i].x] + dis[e[i].y] + e[i].w);

 }

 void prework2(void)

 {

     using namespace masiro;

     sort(e + , e +  + edge_cnt);

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

         fa[i] = i;

     for (int i = ; i <= edge_cnt; ++i)

     {

         int fx = find(e[i].x);

         int fy = find(e[i].y);

         if (fx ^ fy)

         {

             fa[fx] = fy;

             addEdge(e[i].x, e[i].y, e[i].w);

         }

     }

     root = n + ; 

     for (int i = ; i <= s; ++i)

         if (find(c[i]) == c[i])

             addEdge(root, c[i], inf);

     dep[root] = ;

     fat[root][] = root;

     memset(mex, , sizeof(mex));

     predfs(root, -);

 }

 int lca(int x, int y)

 {

     using namespace masiro;

     int res = ;

     if (dep[x] < dep[y])

         swap(x, y);

     for (int i = ; i >= ; --i)

         if (dep[fat[x][i]] >= dep[y])

         {

             res = max(res, mex[x][i]);

             x = fat[x][i];

         }

     if (x == y)

         return res;

     for (int i = ; i >= ; --i)

         if (fat[x][i] != fat[y][i])

         {

             res = max(res, mex[x][i]);

             res = max(res, mex[y][i]);

             x = fat[x][i];

             y = fat[y][i];

         }

     res = max(res, mex[x][]);

     res = max(res, mex[y][]);

     return res;

 }

 signed main(void)

 {

     scanf("%d%d%d", &n, &s, &m);

     for (int i = ; i <= s; ++i)

         scanf("%d", c + i);

     memset(kirito::hd, -, sizeof(kirito::hd));

     memset(masiro::hd, -, sizeof(masiro::hd));

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

     {

         int x, y, w; scanf("%d%d%d", &x, &y, &w);

         kirito::addEdge(x, y, w);

         kirito::e[i] = edge(x, y, w);

     }

     prework1();

     prework2(); 

     int q; scanf("%d", &q);

     for (int i = ; i <= q; ++i)

     {

         int x, y, w; scanf("%d%d%d", &x, &y, &w);

         int maxCost = lca(x, y);

         if (w >= maxCost)

             puts("TAK");

         else

             puts("NIE");

     }

 }

BZOJ_4144.cpp

@Author: YouSiki

相关文章