Please read the new rule regarding the restriction on the use of AI tools. ×

ameydhar's blog

Help — UVa 11354
By ameydhar, 11 years ago, In English

I am trying to solve this problem : 11354 — Bond

I am using minimum spanning tree but am not able to proceed after finding the minimum cost subgraph. I am not sure if my approach is correct. I would appreciate any help on the method and implementation.

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

We can answer the queries offline:
Sort edges by cost.
Build DSU (Disjoint Set Union) over vertices of a graph.
Add edges one by one and each time we union two separeate sets we can answer subset of queries such that s[i] in one of the set and t[i] is in the other. The answer is the cost of current edge.
To understand that this situation happens and answer queries you can use hashtables for each of subsets.
Initially each vertex in his own subset. And each subset has it's own hashtable. Add query i into two hashtables: one for t[i] and one for s[i]. When we join two subsets we have to add all queries from the smaller hashtable into the larger one. All queries contained by both hashtables can be answered right now. Complexity of this merging will be Q log Q because we merge smaller table into the larger one.
**PS:** You can use std::set in C++ but the total complexity will be Q (log Q)^2

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

    can anyone explain me your negative votes? the code

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

    I don't know what the community here looks for, but I upvoted your answer. Thanks a lot :)

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Also there is an online algorithm with (N log N + M log M) graph preprocessing:
1) build a minimal spanning tree
2) select any vertex as root.
3) during the dfs remember for each vertex i it's p[i][0] — parent, p[i][1] — second parent, p[i][2] 4-th parent .. p[i][k] — 2^k th parent. Along with the parents can store w[i][k] — maximal weight of the edges between vertex i and it's 2^k th parent. Also for each vertex we have to remember it's distance from the root.
4) to process a query (x, y) you have to find z = LCA(x, y) (Least Common Ancestor) using above information about parents in O(log(n)). At the same time you can find maximal weight between z and y, and between z and y

→ Reply