Given a weighted undirected graph, you have multiple queries asking for the minimum possible maximum edge between two points. How do you solve this?
N<=100000 Q<=100000
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Given a weighted undirected graph, you have multiple queries asking for the minimum possible maximum edge between two points. How do you solve this?
N<=100000 Q<=100000
Название |
---|
Auto comment: topic has been updated by iLoveIOI (previous revision, new revision, compare).
You construct a maximum spanning tree / forest (the spanning tree/forest with greatest total sum of edge weights). You can prove that the minimum possible maximum edge between two points is the minimum edge in the path between two points in the spanning tree / forest (If you cannot feel free to Google it).
So the problem shrinks into the following: given a tree and multiple queries: (u, v) please print out the maximum edge weight in the path between (u, v). A lot of solutions have been mentioned, one of them is offline query using Disjoint Set Union, another is using sparse table (same technique used in Lowest Common Ancestor problem). The key word to Google is "second MST" I think.
How do you use DSU?
Ah, it's complicated, but I should try for a decent explanation here.
Suppose you have n set, each set contains index of queries. For example if the i-th query is (X, Y) then both set[X] and set[Y] contain i.
Try merge each edge to form a maximum spanning tree / forest like in Kruskal algorithm. Suppose you are trying to merge edge (u, v).
Observe that for every node x inside the connected component of node root(u) and y inside the connected component of node root(v), the minimum edge weight on the path between x and y in the MST is the weight of the edge (u, v), because the edge (u, v) is the latest edge that connects x and y (which means with edge (u, v), we finally reach the state where x and y belong to the same connected component).
Based on that observation, let say set[root(u)].size < set[root(v)].size, for every query i inside set[root(u)], if it's appear on set[root(v)], the answer for i-th query is weight(u, v). After successfully answer i-th query, you should delete them from both set.
After answering all possible queries in the step of adding edge (u, v), you should merge the set[root(u)] to set[root(v)]. Since we assume set[root(u)].size < set[root(v)].size, we are merging small set to large set. Small-to-large, combining with path compression, are the most powerful feature of DSU which lower the overall complexity of this data structure.
In C++, you can use std::set. The overall complexity is O((Q + N)logN).
Is there a more memory-efficient way?
After construction of the maximum spanning tree you can use MO's algorithm.
Do you have sample code
Can you provide link of the problem?
For example Imperial Roads (URI 2703 or LA 8196), Earth Sled Tour (URI 2933), Trucks (URI 1476 or UVa 12655).