Блог пользователя iLoveIOI

Автор iLoveIOI, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by iLoveIOI (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    How do you use DSU?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you provide link of the problem?