今天來寫次小生成樹!
題目：
求出最小生成樹及次小生成樹的花費，其中次小為非嚴格。
做法：
最小生成樹大家都會做
我們用Kruskal貪心選出最小生成樹
而次小，就是將某條邊與樹外的邊替換後最小的那一棵
此題的N=100，暴力枚舉就可以過了
枚舉N-1條樹上的邊，忽略該條後重新建一次MST，紀錄最小的花費
這個方法似乎跟之前的MST唯一性有點相似?!
若重建的MST花費與最小生成樹花費相同，代表不唯一
換句話說，次小生成樹(非嚴格)花費與最小一樣，此圖的MST當然不唯一
聽起來很像廢話(?
總之一樣的方法，我們現在可以拿來求次小生成樹!
code:
沒有留言:
張貼留言