Hello Codeforces Community!
Today I have studied the problem of finding the minimum spanning tree in a directed graph.
This problem is solved using the two Chinese algorithm (Chu-Liu / Edmonds' algorithm). You can read more about this algorithm in Russian using google translator in Oleg Davydov's blog A little about minimal spanning trees, in the ITMO wiki, here, AlgoCode Wiki. In English you can read in detail: Wikipedia, Tarjan's notes, Uri Zwick's detailed post.
I want to practice solving problems on this topic, but while searching I found very few problems.
Let's create a Codeforces sheet from tasks on this topic! Please help me with this! Share with the problem if you have solved on this topic.
Problems List:
- Smallest Weight Arborescence problem
- Div 1 900 Topcoder SRM 584
- LightOJ problems
- UVa :: 11183 — Teen Girl Squad.
- Problem D from NEERC 2013
- Road Repairs
- Fastest Speedrun
- Operation "Steak or boil" (use google translate)
- Task 4. Monitoring pipes (All-Russian Olympiad for schoolchildren in Informatics, regional stage, first round, January 27, 2018)
(use google translate) - Tasks from LKSH2018-A (only statements are available,use google translate)
This website contains four problems related to minimum arborescence.
Thank you !