al13n's blog

By al13n, 10 years ago, translation, In English
First note that a valid graph of wormholes is either connected or consists of two connectivity components with one exit in each. The proof is in the end of this text. Also note that the first option is never optimal because one edge can be removed to get the second option. Let's build a minimal spanning tree of the input graph. If it contains more than two components, the answer for each query is -1. If it contains two components, the answer is -1 if both objects are in the same component, and the weight of the spanning tree otherwise. The most interesting case is one component: we need to cut the spanning tree into two trees containing one exit each and having minimal sum of weights (not actually cut but get the sum of weights of the resulting trees). It can be done by (virtually) removing the most heavy edge on the path between the exits; so the only thing we need to know is the weight of such edge. It can be done with LCA algorithm: for each node precalculate upward jumps of height 2^k, k=0..log n, but also for each jump calculate the maximum weight of an edge on the path of this jump. Then you can split the path a-b in paths a-lca(a,b) and b-lca(a,b) and calculate the maximum weight on each of them in O(log n) using the precalculated values.
Now the proof:
First, it's easy to see that such graph of wormholes is valid: we can enter any exit, cross all tunnels in this component, go to another component (there is always an edge between components because tunnel graph is connected), cross all tunnels there, cross all remaining tunnels between components and leave using one of the exits. Besides these components A and B let there be another component C (and maybe some other components) and the number of tunnels between A and C is odd, between B and C - even; in this case it's impossible to traverse all tunnels once and return to A or B, so this wormhole graph is invalid. If both exits are in the same component and there is another component and the number of tunnels between them is odd, it's invalid too. So the only options left are those mentioned in the beginning.
  • Vote: I like it
  • +15
  • Vote: I do not like it