determinism's blog

436C — Dungeons and Candies
By determinism, 10 years ago, In English

In the solution of tutorial of this problem, levels are represented by vertices and transfers are represented by edges. Graph also has a start vertex. It says that the result is a minimum spanning tree of the graph. I couldn't understand why the answer is a minimum spanning tree. Can't a vertex of a minimum spanning tree have more than one adjacent vertex which is impossible for a tree to be the result? Can someone explain where I'm wrong?

Tags mst
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Consider a directed graph. Edge (A -> B) means that you use level A as a base, or send level B entirely if A == 0. There are obviously no cycles, and each vertex but 0 has exactly one edge that enters it. So this graph is always a tree as you can see.

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

    I understood that the result is a tree. What I could't understand was how a minimal spanning tree always fulfils the requirement that for each vertex you can only go to one vertex. For instance, minimum spanning tree could have every edge from vertex 0 to others.

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

      Well I don't really understand what you mean. If you go by dfs(0), all conditions will take place

      → Reply