算法合集之淺析二分圖匹配在信息學(xué)競(jìng)賽中的應(yīng)用(參考版)
2024-10-19 20:32本頁(yè)面
【正文】 ?正是通過 猜想 將權(quán)值由圖中的邊轉(zhuǎn)移到頂點(diǎn)上，重新構(gòu)造二分圖，才得到了更為優(yōu)秀的算法二！ 總結(jié) 信息學(xué)競(jìng)賽中的各種題目，往往都需要通過對(duì)題目的仔細(xì) 觀察 ，構(gòu)造出合適的數(shù)學(xué)模型，然后通過對(duì)題目以及模型的進(jìn)一步 分析 ， 挖掘出問題的本質(zhì)，進(jìn)行大膽的 猜想 ，轉(zhuǎn)化模型， 設(shè)計(jì)優(yōu)秀的算法解決問題。 回顧 ?通過對(duì)最小生成樹性質(zhì)的 分析 得到一組不等式 Dv≤Du。結(jié)點(diǎn) i的 Pathi中的。 所以 Y39。的匹配邊數(shù)都不超過 n1，所以該子圖的點(diǎn)數(shù)為 O(n)，邊數(shù)為 O(n2)。結(jié)點(diǎn)以及它們之間的邊構(gòu)成的子二分圖。 i0 j1 i1 j2 i2 jk ik 復(fù)雜度分析 也就是說我們?cè)诟?R和 Path時(shí)只需要處理X39。 O(n3) 復(fù)雜度分析 前三個(gè)操作復(fù)雜度都顯而易見，下面討論操作 4的時(shí)間復(fù)雜度。； O(n) 2 詢問是否存在 q的某個(gè)鄰結(jié)點(diǎn) p為可匹配點(diǎn)； O(mn)=O(n3) 1 將所有 Y39。 R和 Path jm j ← j + 1 結(jié)束 N N Y Y 復(fù)雜度分析 下面來分析一下該算法的時(shí)間復(fù)雜度。 P和 Path j ← 1 q ← Y39。 下面給出算法的流程： 將 Y39。結(jié)點(diǎn) j的鄰結(jié)點(diǎn)集合， Y39。結(jié)點(diǎn)有一條可增廣路徑到達(dá)點(diǎn) i，其路徑用 Pathi來表示。 算法分析 用 R來記錄可匹配點(diǎn)，如果 X39。結(jié)點(diǎn)都盡量找到權(quán)值較小的 Y39。 那么可以將所有的 Y39。的值只與 Y39。的權(quán)值都集中在 Y39。的最小權(quán)完備匹配。最小權(quán)完備匹配。 又因?yàn)?M和 M39。 所以當(dāng) SM取到最大值時(shí)， SM39。 X Y 算法分析 因?yàn)?SM+SM39。 μ=6+2+5+7=20 X39。為：(1,7),(2,2),(3,5),(4,6) SM39。 5 2 6 7 3 2 4 2 2 5 0 圖 G中這個(gè)完備匹配 M為：(1,7),(2,8),(3,5),(4,6) SM=2+0+2+5=9 圖 G39。 Y39。 1 1 2 2 3 3 4 4 5 6 7 1 2 3 4 5 6 7 8 圖 G 圖 G39。中的一條匹配邊 (i， j) 這里將介紹如何找到圖 G中匹配 M對(duì)應(yīng)的圖G39。 對(duì)于圖 G中實(shí)結(jié)點(diǎn) Xi的匹配邊 (i， j)∈ M， 若 Wi,j=0,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1