算法合集之淺談圖論模型的建立與應(yīng)用(編輯修改稿)
2024-11-12 20:33 本頁面
【文章內(nèi)容簡(jiǎn)介】 ]S[i1]≤Wi (0≤i≤23) S[i]S[i8]≥Ri (8≤i≤23) S[23]+S[i]S[i+16]≥Ri (0≤i≤7) 例題 2 出納員的雇傭 （ ACM Tehran 2021） 分析 這樣的不等式組，不禁使我們想到了差分約束系統(tǒng)。 對(duì)于每個(gè)不等式 S[i]S[j]≤K，從頂點(diǎn)ｊ向頂點(diǎn)ｉ引一條權(quán)值為 K的有向邊。我們要求 S[23]的最小值，就是要求頂點(diǎn)0到頂點(diǎn) 23的最短路。 注意上面第三條不等式：它包含三個(gè)未知數(shù)，無法在圖中表示為邊的關(guān)系。 0≤S[i]S[i1]≤Wi (0≤i≤23) S[i]S[i8]≥Ri (8≤i≤23) S[23]+S[i]S[i+16]≥Ri (0≤i≤7) 怎么辦 例題 2 出納員的雇傭 （ ACM Tehran 2021） 分析 退一步考慮：如果 S[23]已經(jīng)確定了，那么上面的不等式組可以完全轉(zhuǎn)化為一個(gè)有向圖，頂點(diǎn) 0到頂點(diǎn)ｉ的最短路，就是 S[i]的解。而當(dāng)圖中存在負(fù)權(quán)回路時(shí)，不等式組無解。 至于 S[23]，我們可以用二分法枚舉，逐步縮小范圍，用迭代法判斷是否存在負(fù)權(quán)回路（判定可行性），最終求得S[23]的最小值。時(shí)間復(fù)雜度為 O(243*log2N)。 0≤S[i]S[i1]≤Wi (0≤i≤23) S[i]S[i8]≥Ri (8≤i≤23) S[23]+S[i]S[i+16]≥Ri (0≤i≤7) 例題 2 出納員的雇傭 （ ACM Tehran 2021） 小結(jié) 本題用到了差分約束系統(tǒng)的理論，在競(jìng)賽中，這樣的系統(tǒng)并不多見，但是卻可以巧妙的解決一些難題。這類題目的模型都不明顯，需要一定的思考和轉(zhuǎn)化。做這類題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長(zhǎng)路模型。 例題 3 貪婪之島 （ ZOJ） 問題描述 有 N（ N≤100000）張卡片，每張卡片有三種能力，每種能力的能力值分別為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1