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

POI[2012] Tour de Byteotia
Автор saba_tavdgiridze, история, 9 лет назад, По-английски

Can anyone give me an idea how to solve this problem ? Tour de Byteotia Thanks in advance!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

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

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

Am I right or it is enough to find any spanning tree and delete other edges?

Apart from that, POIs have editorials. Try searching oi.edu.pl website

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

    You're wrong since the graph is not necessarily connected, hence it can have no spanning tree.
    By the way, even if the input graph always had a spanning tree, the solution would be still wrong.
    Simply consider a clique, where you would add N - 1 edges and at least is possible.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Let's try to add the maximum amount of edges so that no cycle passes through vertices 1..K.
You can first of all add all "safe" edges (x; y) — those which have x>K and y>K.
After that, iterate through the others, and add an edge only in case it won't form a cycle (this can be checked with the help of DSU).
After we're done, the answer is formed by the edges we didn't add.

→ Ответить