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

Автор star569, 10 лет назад, По-английски

Hi Codeforces,

I'm going to IOI this year and I'm currently preparing for it. My teammates have recommended this site to me and I have registered here today. This site looks great so far :)

Anyway, back to the original topic. As graph theory is an important component in IOI, I'm currently preparing hard for it. I know that direct implementations of the standard graph algorithms will not be tested in IOI, so I'm trying to think of variations and applications of some standard algorithms. I have thought of these so far for MST and Dijkstra.

  • MST

  • Find number of unique MST

  • Find MST that doesn't use a certain edge/certain edges
  • Minimum Spanning Forest
  • Second best spanning tree
  • Dijkstra

  • Find number of shortest paths
  • Find shortest path with minimum/maximum/certain number of edges for a weighted graph
  • Find shortest path that passes through a certain vertex/certain vertices/a certain edge/certain edges
  • Second best shortest path

I would really appreciate it if anyone can help provide descriptions of possible solutions for the above variations. I would also appreciate it if anyone can state more variations of the common algorithms(not just these two) that I have not listed above.

Thank you!~

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

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
Second best spanning tree:
1 - Run MST and find edges which is used in MST. (MST edges)
2 - For every MST edges, remove this edge in graph, run MST in graph, find max, add this edge to graph.