laituanksa245's blog

Minimum Spanning Tree Problems
By laituanksa245, 12 years ago, In English

I have just learnt about MST.

Can anyone suggest me some problems on Codeforces's problem set that are related to MST ?

Thanks.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it's better for you to search in problemset but among all problems I saw in CF, I think 160D - Edges in MST is best one.

good luck

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

From this blog Link

http://mirror.codeforces.com/contest/908/problem/F (5) //[VERY NICE] //Not exactly MST but similar[GREEDY]

http://mirror.codeforces.com/contest/125/problem/E (5) //[BS]

http://mirror.codeforces.com/contest/76/problem/A (4) //[VERY NICE] Sort by A and KEEP spanning + one edge

LA 6622 — Absurdistan Roads (4) //Plus one edge

UVA 12176

UVA 10600

UVA 10724

https://www.hackerrank.com/contests/june-world-codesprint/challenges/johnland

UVA 11710

Gym 101252C [2014-2015 CT S02E05: Codeforces Trainings Season 2 Episode 5 — 2009-2010 ACM-ICPC]

Gym 101047I [2015 USP Try-outs][HARD]

UVA 11183 [Directed]

LightOJ 1101

https://www.codechef.com/problems/CHEFELEC

UVA 10307

http://mirror.codeforces.com/problemset/problem/598/D

http://mirror.codeforces.com/problemset/problem/32/C

http://mirror.codeforces.com/problemset/problem/744/A

https://devskill.com/CodingProblems/ViewProblem/344

908 — Re-connecting Computer Sites [UVA]

1208 — Oreon [UVA]

1235 — Anti Brute Force Lock [UVA]

10034 — Freckles [UVA]

11228 — Transportation system [UVA]

11631 — Dark roads [UVA]

11733 — Airports [UVA]

11747 — Heavy Cycle Edges [UVA]

BLINNET SPOJ (3)

11183 UVA (4) //Directed [need to know algo!]

http://www.spoj.com/problems/ULM09/ (3) //Sum-Kruskal

http://www.spoj.com/problems/IITKWPCG/ (4) //VERY NICE [log instead of price]

http://mirror.codeforces.com/contest/17/problem/B (3) //Spanning tree [no dsu]

→ Reply