首页 > 代码库 > BZOJ 4144: [AMPPZ2014]Petrol

BZOJ 4144: [AMPPZ2014]Petrol

2024-08-22 15:15:43   220人阅读

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

鸣谢Claris上传

[Submit][Status][Discuss]

 

分析

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

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

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

代码

技术分享 
  1 #include <cmath>
  2 #include <queue>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <iostream>
  7 #include <algorithm>
  8 
  9 using namespace std;
 10 
 11 #define N 500005
 12 #define inf 0x3f3f3f3f
 13 
 14 int n, m, s, c[N];
 15 
 16 struct edge
 17 {
 18     int x, y, w;
 19     
 20     edge(void) {};
 21     edge(int _x, int _y, int _w) :
 22         x(_x), y(_y), w(_w) {};
 23         
 24     friend bool operator < (const edge &a, const edge &b)
 25     {
 26         return a.w < b.w;
 27     }
 28 };
 29 
 30 struct step
 31 {
 32     int id, dis;
 33     
 34     step(void) {};
 35     step(int a, int b) :
 36         id(a), dis(b) {};
 37         
 38     friend bool operator < (const step &a, const step &b)
 39     {
 40         return a.dis > b.dis;
 41     }
 42 };
 43 
 44 namespace kirito
 45 {
 46     edge e[N]; int edge_cnt = 0;
 47     
 48     int hd[N], to[N], vl[N], nt[N], tot;
 49     
 50     void addEdge(int x, int y, int w)
 51     {
 52         nt[tot] = hd[x]; to[tot] = y; vl[tot] = w; hd[x] = tot++;
 53         nt[tot] = hd[y]; to[tot] = x; vl[tot] = w; hd[y] = tot++;
 54     }
 55     
 56     int dis[N], from[N]; 
 57     
 58     priority_queue<step> pq;
 59 }
 60 
 61 namespace masiro
 62 {
 63     edge e[N]; int edge_cnt = 0;
 64     
 65     void pushEdge(int x, int y, int w)
 66     {
 67         e[++edge_cnt] = edge(x, y, w);
 68     }
 69     
 70     int hd[N], to[N], vl[N], nt[N], tot;
 71     
 72     void addEdge(int x, int y, int w)
 73     {
 74         nt[tot] = hd[x]; to[tot] = y; vl[tot] = w; hd[x] = tot++;
 75         nt[tot] = hd[y]; to[tot] = x; vl[tot] = w; hd[y] = tot++;
 76     }
 77     
 78     int fa[N];
 79     
 80     int find(int u)
 81     {
 82         return fa[u] == u ? u : fa[u] = find(fa[u]);
 83     }
 84     
 85     int root;
 86     
 87     int dep[N], fat[N][30], mex[N][30];
 88     
 89     void predfs(int u, int f)
 90     {
 91         for (int i = 1; i < 30; ++i)
 92         {
 93             fat[u][i] = fat[fat[u][i - 1]][i - 1];
 94             mex[u][i] = max(mex[u][i - 1], mex[fat[u][i - 1]][i - 1]);
 95         }
 96         
 97         for (int i = hd[u]; ~i; i = nt[i])
 98             if (to[i] != f)
 99             {
100                 dep[to[i]] = dep[u] + 1;
101                 mex[to[i]][0] = vl[i];
102                 fat[to[i]][0] = u;
103                 predfs(to[i], u);
104             }
105     }
106 }
107 
108 void prework1(void)
109 {
110     using namespace kirito;
111     
112     memset(dis, inf, sizeof(dis)); 
113     
114     for (int i = 1; i <= s; ++i)
115     {
116         dis[c[i]] = 0;
117         from[c[i]] = c[i];
118         pq.push(step(c[i], 0));
119     }
120     
121     while (!pq.empty())
122     {
123         step top = pq.top(); pq.pop();
124         
125         if (dis[top.id] != top.dis)
126             continue;
127             
128         for (int i = hd[top.id]; ~i; i = nt[i])
129             if (dis[to[i]] > vl[i] + top.dis)
130             {
131                 from[to[i]] = from[top.id];
132                 dis[to[i]] = vl[i] + top.dis;
133                 pq.push(step(to[i], dis[to[i]]));
134             }
135     }
136     
137     for (int i = 1; i <= m; ++i)
138         if (from[e[i].x] ^ from[e[i].y])
139             masiro::pushEdge(from[e[i].x], from[e[i].y], dis[e[i].x] + dis[e[i].y] + e[i].w);
140 }
141 
142 void prework2(void)
143 {
144     using namespace masiro;
145     
146     sort(e + 1, e + 1 + edge_cnt);
147     
148     for (int i = 1; i <= n; ++i)
149         fa[i] = i;
150         
151     for (int i = 1; i <= edge_cnt; ++i)
152     {
153         int fx = find(e[i].x);
154         int fy = find(e[i].y);
155         
156         if (fx ^ fy)
157         {
158             fa[fx] = fy;
159             addEdge(e[i].x, e[i].y, e[i].w);
160         }
161     }
162     
163     root = n + 1; 
164     
165     for (int i = 1; i <= s; ++i)
166         if (find(c[i]) == c[i])
167             addEdge(root, c[i], inf);
168     
169     dep[root] = 1;
170     fat[root][0] = root;
171     memset(mex, 0, sizeof(mex));
172     
173     predfs(root, -1);
174 }
175 
176 int lca(int x, int y)
177 {
178     using namespace masiro;
179     
180     int res = 0;
181     
182     if (dep[x] < dep[y])
183         swap(x, y);
184         
185     for (int i = 25; i >= 0; --i)
186         if (dep[fat[x][i]] >= dep[y])
187         {
188             res = max(res, mex[x][i]);
189             x = fat[x][i];
190         }
191         
192     if (x == y)
193         return res;
194         
195     for (int i = 25; i >= 0; --i)
196         if (fat[x][i] != fat[y][i])
197         {
198             res = max(res, mex[x][i]);
199             res = max(res, mex[y][i]);
200             x = fat[x][i];
201             y = fat[y][i];
202         }
203         
204     res = max(res, mex[x][0]);
205     res = max(res, mex[y][0]);
206     
207     return res;
208 }
209 
210 signed main(void)
211 {
212     scanf("%d%d%d", &n, &s, &m);
213     
214     for (int i = 1; i <= s; ++i)
215         scanf("%d", c + i);
216         
217     memset(kirito::hd, -1, sizeof(kirito::hd));
218     memset(masiro::hd, -1, sizeof(masiro::hd));
219         
220     for (int i = 1; i <= m; ++i)
221     {
222         int x, y, w; scanf("%d%d%d", &x, &y, &w);
223         
224         kirito::addEdge(x, y, w);
225         kirito::e[i] = edge(x, y, w);
226     }
227     
228     prework1(); 
229     prework2(); 
230     
231     int q; scanf("%d", &q);
232     
233     for (int i = 1; i <= q; ++i)
234     {
235         int x, y, w; scanf("%d%d%d", &x, &y, &w);
236         
237         int maxCost = lca(x, y);
238         
239         if (w >= maxCost)
240             puts("TAK");
241         else
242             puts("NIE");
243     }
244 }
BZOJ_4144.cpp

 

@Author: YouSiki

BZOJ 4144: [AMPPZ2014]Petrol


联系
我们