高中生程式解題系統

#36932: 解題想法

學校 : 高雄市立前鎮高級中學
編號 : 119456
來源 : [140.114.216.100]
最後登入時間：
2024-03-24 11:15:22

k715. 糧食便道 (Supply) -- TOI 練習賽 202306 潛力組第2題 | From: [61.61.93.180] | 發表日期 : 2023-08-17 11:45

可以建一個虛點 P，讓每個有星號的點都連一條邊權為 0 的邊到 P，然後做最小生成樹。

這樣在做最小生成樹時就不會另外找一條路徑讓兩個帶有星號的連通塊相連了。

#36943: Re: 解題想法

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間：
2024-04-13 22:06:23

k715. 糧食便道 (Supply) -- TOI 練習賽 202306 潛力組第2題 | From: [1.161.160.111] | 發表日期 : 2023-08-18 00:39

可以建一個虛點 P，讓每個有星號的點都連一條邊權為 0 的邊到 P，然後做最小生成樹。

這樣在做最小生成樹時就不會另外找一條路徑讓兩個帶有星號的連通塊相連了。

Daniel 太厲害了

#36945: Re: 解題想法

學校 : 高雄市立前鎮高級中學
編號 : 119456
來源 : [140.114.216.100]
最後登入時間：
2024-03-24 11:15:22

k715. 糧食便道 (Supply) -- TOI 練習賽 202306 潛力組第2題 | From: [61.61.93.180] | 發表日期 : 2023-08-18 05:47

可以建一個虛點 P，讓每個有星號的點都連一條邊權為 0 的邊到 P，然後做最小生成樹。

這樣在做最小生成樹時就不會另外找一條路徑讓兩個帶有星號的連通塊相連了。

Daniel 太厲害了

Daniel07 請不要到處說別人 Daniel，這樣真的太諧了

ZeroJudge Forum