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

436C — Dungeons and Candies
Автор determinism, 10 лет назад, По-английски

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?

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

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

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить