發(fā)布時(shí)間：2021-09-18 09:36

　　本文對(duì)2020年福建省算法冬令營(yíng)數(shù)學(xué)專(zhuān)題上的三道測(cè)試題作了較為詳細(xì)的描述與解答。 

【文章來(lái)源】：福建電腦. 2020,36(03)

【文章頁(yè)數(shù)】：5 頁(yè)

【部分圖文】：

反悔策略

一排樓房才能滿(mǎn)足計(jì)劃圖的要求？n,h≤1,000,0001.2解題思路考慮隱式圖。圖中的每一個(gè)結(jié)點(diǎn)表示一個(gè)當(dāng)前的搭建狀態(tài)。一個(gè)點(diǎn)向另一個(gè)點(diǎn)連邊當(dāng)且僅當(dāng)前一個(gè)點(diǎn)對(duì)應(yīng)的狀態(tài)能夠通過(guò)一次操作變?yōu)楹笠粋�(gè)點(diǎn)對(duì)應(yīng)的狀態(tài)。想要找一條從初始狀態(tài)（即已經(jīng)做完前0列）到目標(biāo)狀態(tài)（已經(jīng)做完前n列）的最短路。圖很大，直接找最短路無(wú)異于暴搜�？梢钥紤]一些在圖上走的策略。圖1隱式圖考慮在圖上貪心地亂走，可能會(huì)走到某一個(gè)奇怪的點(diǎn)，那么這個(gè)點(diǎn)可能根本無(wú)法以最短路到達(dá)終點(diǎn)，顯然不可齲圖2貪心處理隱式圖的問(wèn)題圖3增加樸素反悔邊的隱式圖那如果在圖中加上邊權(quán)為對(duì)應(yīng)邊的邊權(quán)的相反數(shù)的反悔邊呢？那么不論在圖上怎么亂走，依然可以有一條最短路能讓我們走到終點(diǎn)。但是怎樣才能找到這條路呢？因此我們考慮另一種反悔邊。它的邊權(quán)是正整

增加樸素反悔邊的隱式圖那如果在圖中加上邊權(quán)為對(duì)應(yīng)邊的邊權(quán)的相


本文編號(hào)：3399903