iLoveIOI's blog

All pairs minimax
By iLoveIOI, history, 5 years ago, In English

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

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    How do you use DSU?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide link of the problem?

→ Reply