發表新討論
#36932: 解題想法


frankleeplayminecraft58@gmail. ... (LJH-code)

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

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

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

#36943: Re: 解題想法


fire5386 (becaidorz)

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

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

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


Daniel 太厲害了

#36945: Re: 解題想法


frankleeplayminecraft58@gmail. ... (LJH-code)

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

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

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


Daniel 太厲害了


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

ZeroJudge Forum