用匈牙利算法解決相親類型問題的數(shù)學(xué)模型.doc

《用匈牙利算法解決相親類型問題的數(shù)學(xué)模型.doc》由會員分享，可在線閱讀，更多相關(guān)《用匈牙利算法解決相親類型問題的數(shù)學(xué)模型.doc（17頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

關(guān)于玫瑰有約的數(shù)學(xué)模型 摘要：現(xiàn)在城市大齡青年的婚姻問題收起了社會的廣泛關(guān)注，針對這一社會現(xiàn)象，我們假設(shè)某單位有20對大齡青年男女，每個人的基本條件都不相同，并且每個人的擇偶條件也不相同。該單位的婦聯(lián)組織擬根據(jù)他們的年齡，基本條件和要求條件牽線搭橋。本文根據(jù)每個人的情況和要求，建立數(shù)學(xué)模型幫助婦聯(lián)解決3個問題。 關(guān)鍵詞：數(shù)學(xué)模型；滿意度；匈牙利算法；KM算法 The mathematical model about making an appointment for life Li wei (Department of Mathematics and Computational Science Hunan University of Science and Engineering,Yongzhou,425100,Hunan） Abstract: Nowadays, the problem of the young’s marriage has roused more and more public’s concern. According to this phenomenon, we assume that there are twenty pairs of aged people in a company, all of which have different basic condition and their demanding。The Women's Federation of this company wants to wire-pull for them on the basis of their age, basic condition and demand. This paper, according to everyone’s condition and demands, helps the Women's Federation solving this problem. Key words: mathematical model; the measurement of satisfaction; Hungary algorithm; KM algorithm; 1.引言 現(xiàn)在在城市大齡青年的婚姻問題引起了社會的廣泛關(guān)注，針對這一現(xiàn)象，我們給出20對青年男女的基本條件和擇偶條件的抽樣是真實(shí)可靠的。首先，我們將所給的兩個表格按年齡升序重新進(jìn)行排列，分別編號為1，2，3……20。并且將外貌、性格、氣質(zhì)、事業(yè)、財(cái)富五個方面的五個等級A、B、C、D、E分別賦值為5、4、3、2、1，這樣我們就得到了男女青年的基本條件和要求條件的四個矩陣；其次，我們定義了“滿意度”的概念，利用圖論（二部圖）的方法解決這個問題。 在模型中，根據(jù)男青年的基本條件和女青年的要求條件構(gòu)造度量矩陣（權(quán)值矩陣）A，男1號的基本條件和女1號的要求條件，比如在外貌方面，男1號滿足女1號的要求則賦值為5-3+1，在事業(yè)方面，男1號不滿足女1號的要求，則賦值為0，按照這個方法，如果滿足條件則按公式（男青年基本條件值-女青年相應(yīng)的要求條件+1）賦值，反之賦值為0，這樣可以得到外貌，性格，氣質(zhì)，事業(yè)，財(cái)富五個方面的數(shù)值，并將這些數(shù)值相加得到，最終得到權(quán)值矩陣T=（）2020，同理可得，女青年的基本條件和男青年的要求條件所構(gòu)成的權(quán)值矩陣S=()2020，那么男女青年配對的總權(quán)值矩陣（即為滿意度矩陣）為R1=T+S，（因?yàn)楸硎灸衖號的基本條件對j號的要求條件，表示女j號的基本條件對男i號的要求條件，那么用+ 表示男i號對女j號的總權(quán)數(shù)即為他們之間的滿意度）：再次，我們根據(jù)年齡的限制在矩陣R1中將不滿足條件的賦0，得到矩陣R，利用匈牙利算法可得到問題（1）的結(jié)果。再在矩陣R中將大于2的數(shù)字賦1反之賦0，再利用KM算法可得問題（2）的結(jié)果。 由于以上的模型在構(gòu)造權(quán)值矩陣R時，男青年基本條件不滿足女青年要求條件時賦值為0，實(shí)際上還存在男女青年的失望度，故在模型改進(jìn)中針對失望度將模型中賦值為0的另外賦值為（女青年要求條件值–男青年相應(yīng)的基本條件值）即考慮到可能單向面的滿意度較大而另一方面的失望度也較大時同樣不能配對成功，且在把模型無向化時是采用把每個結(jié)點(diǎn)分成兩個結(jié)點(diǎn)的方法即把有向的平行邊分成各自帶自己權(quán)的無向邊，同時在此模型中將初等模型中的五個等級A、B、C、D、E量化為9、7、5、3、1（由于模型中的賦值尺度比較粗糙），其余的步驟與模型相同，從而得到了模型改進(jìn)。 2.問題的提出 目前，在許多城市大齡青年的婚姻問題已引起了婦聯(lián)和社會團(tuán)體組織的關(guān)注。某單位現(xiàn)在有20對大齡青年男女，每個人的基本條件都不相同，如外貌、性格、氣質(zhì)、事業(yè)、財(cái)富等。每項(xiàng)條件通?？梢苑譃槲鍌€等級A、B、C、D、E，如外貌、性格、氣質(zhì)、事業(yè)可分為很好、好、較好、一般、差；財(cái)富可以分為很多、多、較多、一般、少。每個人的擇偶條件也不盡相同，即對每項(xiàng)基本條件的要求是不同的。該單位的婦聯(lián)組織擬根據(jù)他（她）們的年齡、基本條件和要求條件進(jìn)行牽線搭橋。下面給出20對大齡青年男女的年齡、基本條件和要求條件（如下表）。一般認(rèn)為，男青年至多比女青年的年齡大5歲，或女青年的年齡比男青 年的大2歲，并且要至少滿足個人要求5項(xiàng)條件中的2項(xiàng)，才有可能配對成功。本文根據(jù)每個人的情況要求，建立數(shù)學(xué)模型幫助婦聯(lián)解決如下問題： (1)給出可能的配對方案，使得在盡量滿足個人要求的條件下，使得配對成功率盡可能的高。 (2)給出一種20對男女青年可同時配對的最佳方案，使得全部配對成功的可能性最大。 (3)假設(shè)男女雙方都相互了解了對方的條件和要求，讓每一個人出一次選擇，只有當(dāng)男女雙方相互選中對方時才認(rèn)為配對成功，每一個人只有一次選擇機(jī)會。怎樣告訴20對男女青年都應(yīng)該如何做出選擇，使得自己的成功的可能性最大？選擇的方案最多能配對成功多少對？ 男 青 年 基本條件 要求條件 外 貌 性格 氣質(zhì) 事業(yè) 財(cái)富 年 齡 外 貌 性格 氣質(zhì) 事業(yè) 財(cái)富 A C B C A 29 A A C B D C A B A D 29 B A B B C B B A B B 28 B A A B C C A B B D 28 C A B C D D B C A A 30 C B B B E C B C B B 28 B B C D C A B B D C 30 C B B D C B A B C D 30 A B C C D A D C E B 28 A A A C C D B A A A 28 A B A D E B A C D A 32 A B C D B A B C A B 29 B A B B C B A D E C 28 A C B B C A A B B D 30 A C C D C A B B C C 28 A A B C D D E B A A 30 A A A E E C A B A D 28 A A A E E A B A C B 31 B B A C C C D A A A 29 A B A E D A B C D E 27 B C B D B 女 青 年 基 本 條 件 要 求 條 件 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 年齡 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 A C C D A 28 B A B A D B A B A D 25 C B B A B C B A E A 26 B A C B C A B B C D 27 A A B B A B D C E C 25 A B C B B A C B C A 26 B A B B C D C B A B 30 C B A A C A B A E C 31 B A B A B A A A C E 26 C B B B A B C D B B 27 B B A A C A B B C B 28 C B A B C B E C E A 26 A A B B E E A C B B 26 C A B C C B B C A A 25 B A A B D C B A A C 29 B A B B B B A C D C 28 B A B B A A E E D A 25 A A D A C A A B B C 28 C A B A C B A C C E 25 B B B A A D B A C D 29 B B A B B 注：表中的要求條件一般是指不低于所給的條件。 為了方便后面的計(jì)算，我們按年齡升序重新對上述兩個表格進(jìn)行排列并且編號： 男 青 年 基 本 條 件 要 求 條 件 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 年齡 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 1 A B C D E 27 B C B D B 2 B B A B B 28 B A A B C 3 C A B B D 28 C A B C D 4 C B C B B 28 B B C D C 5 A D C E B 28 A A A C C 6 D B A A A 28 A B A D E 7 B A D E C 28 A C B B C 8 A B B C C 28 A A B C D 9 C A B A D 28 B A B B C 10 A C B C A 29 A A C B D 11 C A B A D 29 B A B B C 12 A B C A B 29 B A B B C 13 C D A A A 29 A B A E D 14 D B C A A 30 C B B B E 15 A B B D C 30 C B B D C 16 B A B C D 30 A B C C D 17 A A B B D 30 A C C D C 18 D E B A A 30 A A A E E 19 A B A C B 31 B B A C C 20 B A C D A 32 A B C D B 女 青 年 基 本 條 件 要 求 條 件 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 年齡 外貌 性格 氣質(zhì) 事業(yè) 財(cái)富 1 B A B A D 25 C B B A B 2 B D C E C 25 A B C A B 3 B B C A A 25 B A A B D 4 A E E D A 25 A A D A C 5 B A C C E 25 B B B A A 6 C B A E A 26 B A C B C 7 A C B C A 26 B A B B C 8 A A A C E 26 C B B B A 9 B E C E A 26 A A B B E 10 E A C B B 26 C A B C C 11 A B B C D 27 A A B B A 12 B C D B B 27 B B A A C 13 A C C D A 28 B A B A D 14 A B B C B 28 C B A B C 15 B A C D C 28 B A B B A 16 A A B B C 28 C A B A C 17 C B A A C 29 B A B B B 18 D B A C D 29 B B A B B 19 D C B A B 30 C B A A C 20 A B A E C 31 B A B A B 注：表格中的要求條件一般是指不低于所給條件 3.問題分析 該問題是現(xiàn)實(shí)生活中的實(shí)際問題，主要就是確定合理配對方案，使得在盡量滿足個人要求條件下，使配對成功率盡可能的高。由于每個人的基本條件和要求條件都是給定的，雙方彼此是知道的，而且是相互之間有很大的差異，如果完全按照要求條件組合配對成功。任意一對男女的配對可以看成一個隨機(jī)事件，按某一概率可能配對成功，或不成功。在這里雙方的滿意度主要反映出一個人對另一個人的客觀和主觀看法，因此，滿意度的定義成為解決問題的一個關(guān)鍵。 所謂的“成功率”，就是男女雙方最終配對的概率。實(shí)際上，可以用他們相互之間的滿意度來間接刻畫。相互的滿意度越高，雙方配對的成功率就越大。對于問題（1），要使配對成功率盡可能的高明，也就是給出一種方案，使得20對男女的配對后的滿意度之和最高。 對于問題（2），要使20對男女青年同時配對，使得全部同時成功的可能性（概率）最大。 對于問題（3），因?yàn)槊咳藗€只能選擇一次，能不配對成功取決于雙方是不是選中對方，即要看雙方彼此的滿意度如何。實(shí)際中，假如一個男青年（）對一個女青年（）的滿意度最高，但對的滿意度不一定最高，即若選擇，但不一定選擇。因此，與不一定配成對，反之亦然。現(xiàn)在的問題是誰選誰，使配對成功的可能性最大呢？這個問題實(shí)際上是男女雙方在彼此基本了解的情況下，在保證自己一定滿意的條件下做出自己的選擇，也需要猜測對方會做出怎樣的選擇。因此，這個問題可能轉(zhuǎn)化為男女雙方的對策問題，即轉(zhuǎn)化為求男女雙方的非零和對策的納什平衡點(diǎn)的問題。 4. 模型的假設(shè)與符號說明 4．1模型的假設(shè) (1)題目所給出的男女青年的評價是客觀真實(shí)的; (2)每個人在選擇雙方的時候是理智的; (3)男女青年不會受當(dāng)時環(huán)境的影響。 4．2符號說明 K=1,2,3,4,5.分別表示外貌、性格、氣質(zhì)、事業(yè)、財(cái)富這5個條件； (i=1,2…… 20)表示年齡升序排列后男青年編號； （j=1,2…… 20）表示年齡升序排列后女青年編號； ( i=1,2…… 20,k=1,2,3,4,5)表示男青年在k方面的基本條件； ( i=1,2…… 20,k=1,2,3,4,5)表示男青年在k方面的要求； ( j=1,2…… 20,k=1,2,3,4,5)表示女青年在k方面的基本條件； ( j=1,2…… 20,k=1,2,3,4,5)表示女青年在k方面的要求； 表示男青年i對女青年j在k方面的滿意度； 表示女青年j對男青年i在k方面的滿意度； 表示男青年i與女青年j在k方面的滿意度之和. 5．模型的建立和求解 5.1條件量化處理 對于每個人的外貌、性格、氣質(zhì)、事業(yè)、財(cái)富五項(xiàng)條件的5個等級A，B，C，D，E分別作量化處理為5，4，3，2，1。于是根據(jù)上表可以得到男女青年的基本條件量化矩陣和要求條件量化矩陣（或稱權(quán)值矩陣）以及滿意度分量分別記為： 5.2 滿意度 現(xiàn)在，我們對滿意度進(jìn)行說明，要確定對的第K項(xiàng) 條件的滿意度。先對年齡進(jìn)行篩選，年齡為大于或大于的滿意度為0；如果基本條件達(dá)不到的要求即,給它賦值為0值.否則，滿意度記為剛好達(dá)到為1，超過一個等級加1。即滿意度為。這樣就體現(xiàn)了，當(dāng)一方實(shí)際條件高于對方期望（要求）條件時，則對方對他（她）的好感（相對于要求條件）就會增加，超過得越多，好感增加得越多。 5.3模型的建立 我們把二十個青年男女抽象化為40個結(jié)點(diǎn)得到一個帶權(quán)二部圖，其中Aj表示二十個男青年，Bj表示二十個女青年，而從男青年到女青年有一條帶權(quán)邊，權(quán)則由上面求得的滿意度矩陣決定，然后，我們用最大二部圖匹配算法（匈牙利算法）求出一個最大匹配的解；但是，一開始所求得的是一個有向圖，因此我們必須把它無向化，至此對問題（1）我們僅僅是采用把兩結(jié)點(diǎn)間權(quán)值相加而轉(zhuǎn)化為一個無向圖，進(jìn)而就可以用匈牙利算法對其求解了。而對于問題（2）則要采用圖的完美匹配算法（KM算法）進(jìn)行求解，從而使全部配對成功的可能性最大，對于問題（3），則同樣采用匈牙利算法只是把權(quán)值改變即可，這里我們把結(jié) 點(diǎn)間有向邊的權(quán)值同時大于2且滿意度和不滿意度差別不是很大時才有可能配對成功此時把它賦為1，而在不滿足條件時則賦為0,從而得出能配對成功最多的方案。 下面對匈牙利算法和KM算法進(jìn)行說明。 匈牙利算法的主要思想是在每次增廣的時候不是找一條增廣路而是同時找?guī)讞l點(diǎn)不相交的最短增廣路，形成極大增廣路集，隨后可以沿著這幾條增廣路同時進(jìn)行增廣?？梢宰C明在尋找增廣路集的每一個階段所尋找到的最短增廣路都具有相等的長度，并且隨著算法的進(jìn)行最短增廣路的長度是越來越長的，更進(jìn)一步分析可以證明最多只需增廣ceil(sqrt(n))次就可以得到最大匹配（證明在這里略去）。 KM算法：（全稱是Kuhn-Munkras,是這二個人在1957年提出來的），首先為每個點(diǎn)設(shè)立一個頂標(biāo)Li，設(shè)vi,j-為（i,j）邊的權(quán)，如果可以求得一個完美匹配，使得每條匹配邊vi,，其余邊。此時的解就是最優(yōu)的，因?yàn)槠ヅ溥叺臋?quán)和=，其余任意解的權(quán)和都不可能比這個大。 5.4模型的求解 以題中所給數(shù)據(jù)為例，我們用EXCEL處理后得到權(quán)值，然后編程求得結(jié)果為： 問題(1) 男 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 女 B18 B17 B16 B15 B2 B19 B3 B12 B1 B14 男 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 女 B20 B10 B7 B8 B6 B5 B4 B11 B9 B13 問題(2) 男 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 女 B11 B12 B19 B18 B8 B5 B3 B6 B2 B20 男 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 女 B1 B17 B7 B14 B15 B13 B16 B9 B4 B10 問題(3) 男 A1 A3 A5 A10 A12 A14 A15 A17 A18 A19 女 B15 B18 B19 B9 B2 B6 B4 B14 B11 B8 5.5模型修正 （1）對滿意度的說明 首先要注意到兩個事實(shí)：其一，如果基本條件比的要求條件差得越多，則對的第K項(xiàng)條件的滿意度就越小，反之亦然。也就是說，如果一方的實(shí)際條件比對方期望（要求）的條件差距越大，則對方對另一方失望就越大，即滿意度就越小。其二，如果的基本條件比的要求條件高，則對的第k項(xiàng)條件的滿意度（k）就會增加，但增加不會太多。即當(dāng)一方的實(shí)際條件高于對方期望（要求）的條件時，則對方對加一方的好感（相對要求條件）增加不會太大。 而在模型中只考慮了實(shí)際條件高于要求條件，好感會增加并考慮到實(shí)際條件低于要求條件時，失望會增加，即滿意度會減小。現(xiàn)在模型的基礎(chǔ)上加以改進(jìn)：如果的基本條件達(dá)不到的要求，即（）時，給它賦值它是一個負(fù)值，體現(xiàn)了當(dāng)一方實(shí)際條件低于期望（要求）的條件時，則對方對他（她）失望（相對于要求條件）就會增加差距越大，失望度就越大，相應(yīng)的滿意度就越小。顯然，改進(jìn)后成功的解決了上面所提出的問題，所以顯得更加合理。 滿意度矩陣中的各分量分別表示如下： (2) 模型的重新建立 首先,我們把量化的尺度改為1-9尺度把A,B,C,D,E五個等級分別量化為9、7、5、3、1，然后在給出的二部圖轉(zhuǎn)化為無向圖時則把每個結(jié)點(diǎn)分為兩個結(jié)點(diǎn)，從而問題轉(zhuǎn)化為求40對結(jié)點(diǎn)的二部圖的最大匹配和完美匹配問題了，對問題1和問題2用同樣算法求解，而對于問題3則當(dāng)滿意度矩陣中的權(quán)大于零時賦為1而在小于零時則賦為0。 （3）以題中所給數(shù)據(jù)為例，我們用EXCEL處理后得到權(quán)值，然后編程求得結(jié)果為： 問題(1) 男 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 女 B4 B18 B15 B20 B2 B5 B3 B13 B17 B9 男 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 女 B16 B10 B7 B1 B6 B19 B14 B11 B8 B12 問題(2) 男 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 女 B2 B18 B6 B14 B19 B5 B3 B13 B11 B20 男 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 女 B1 B17 B7 B12 B15 B9 B16 B8 B4 B10 問題(3) 男 A1 A3 A5 A10 A12 A14 A15 A17 A18 A19 女 B15 B18 B19 B9 B2 B6 B4 B14 B11 B8 6. 模型結(jié)果的分析 從所得的結(jié)果分析可知，模型改進(jìn)后所得到的結(jié)果比改進(jìn)前所得到的結(jié)果更加合理，對問題1是為了要盡量滿足個人要求的條件使配對成功率更高，即要使得二部圖中的邊的權(quán)值相對來說是比較大的，而對問題2則是要全部配對成功的可能性最高，即是要使得所得到的完美配對圖的權(quán)值之和最大即使得要20對同進(jìn)配對的可能性最大的方案。而對問題3則要在男女雙方都滿意的前提下并且是雙方都選擇了雙方。則從我們得到的結(jié)果可知模型改進(jìn)后得到的結(jié)果比模型要更優(yōu)。 7. 模型的優(yōu)缺點(diǎn) 對于兩個模型，改進(jìn)前的模型顯然比改進(jìn)后的模型粗糙得多，但是運(yùn)行起來相對簡單，而且在模型中我們運(yùn)用了匈牙利算法使問題更加簡單化，充分體現(xiàn)了熟練運(yùn)用數(shù)學(xué)軟件在我們運(yùn)用數(shù)學(xué)思想解決實(shí)際問題中的重要性。 而在改進(jìn)后的模型中，我們利用圖論的思想，運(yùn)用匈牙利算法（二部圖的最大匹配算法）和KM算法（二部圖的完美匹配算法），并且將原精度提高，采用1-9尺度，使得問題的解答更加精確，但是由于算法太復(fù)雜，在計(jì)算機(jī)計(jì)算方面顯得比較吃力，運(yùn)行也相對難以實(shí)現(xiàn)一點(diǎn)。 在社會上各人的擇偶標(biāo)準(zhǔn)不同，所以他們在選擇對象的側(cè)重點(diǎn)也會不同，比方說；有的人會特別注重外表，然而有的人特別注重對方的事業(yè)和個人的氣質(zhì)等等。 而我們在兩個模型中，只是簡單的將五個方面的五個等級分別賦值為幾個數(shù)值，不能體現(xiàn)個人的側(cè)重點(diǎn)。同時，我們在模型中假設(shè)了對各人的抽樣是真實(shí)可靠的，然而各人的擇偶標(biāo)準(zhǔn)還會隨時間不斷改變，所以假設(shè)不一定會長久成立，若在模型的改進(jìn)方向上再注意這些問題，結(jié)果會更接近現(xiàn)實(shí)。 參考文獻(xiàn) [1]韓中庚.數(shù)學(xué)建模方法及其應(yīng)用[M].北京:高等教育出版社，2005.5. [2]邊馥萍,侯文華,梁馮珍.數(shù)學(xué)模型方法與算法[M].北京:高等教育出版社,2005.4. [3]姜啟源,謝金星.數(shù)學(xué)模型(第三版)[M].北京:高等教育出版社,2003.8. [4]吳乃陵,況迎輝.C++程序設(shè)計(jì)(第二版)[M].北京:高等教育出版社,2006.3. [5] Bczdek J, Pal S. Fuzzy Models for Pattern Recognition [M]. Piscataway: IEEE Press, 1992. [6] zdek J. Pattern Recognition with KM Algorithm [M]. New York: PlenumBe Press, 1981. 致謝 本文的選題得到了林依勤老師的指導(dǎo)，從撰寫到完稿都得到了曾立波老師的悉心指導(dǎo)，在此，對曾立波老師和林依勤老師的幫助表示衷心的感謝。另外本文的完成還得到了羅光輝同學(xué)和李鵬同學(xué)的幫助，在此也對他們表示衷心的感謝。 附 錄 匈牙利算法 #include #include #include using namespace std; bool mark1[100],mark2[100]; int list[100]; int n,m,edge,num;c ector > v; bool dfs(int to) { register int i,point,s = list[to]; for(i=0;i>n) { if(n == 0)break; v.clear(); v.resize(n); cin >> m >> edge; for(i=0;i> j >> s >> d; v[s].push_back(d); } Solve(); } return 0; } KM算法： #include #include #include using namespace std; const int size = 160; const int INF = 100000000;? //? 相對無窮大 bool map[size][size];? ? ? ? ?// 二分圖的相等子圖, map[i][j] = true 代表Xi與Yj有邊 bool xckd[size], yckd[size];? // 標(biāo)記在一次DFS中，Xi與Yi是否在交錯樹上 int match[size];? ? ? ? ? ? ?// 保存匹配信息，其中i為Y中的頂點(diǎn)標(biāo)號，match[i]為X中頂點(diǎn)標(biāo)號 bool DFS(int, const int); void KM_Perfect_Match(const int n, const int edge[][size]) { ? ?int i, j; ? ?int lx[size], ly[size];? ?//? KM算法中Xi與Yi的標(biāo)號 ? ?for(i = 0; i < n; i++) { ? ?? ?lx[i] = -INF; ? ?? ?ly[i] = 0; ? ?? ?for(j = 0; j < n; j++) { ? ?? ?? ?lx[i] = max(lx[i], edge[i][j]); ? ?? ?} ? ?} ? ? bool perfect = false; ? ? while(!perfect) { ? ?? ?//? 初始化鄰接矩陣 ? ? ? ? for(i = 0; i < n; i++) { ? ? ? ? ? ? for(j = 0; j < n; j++) { ? ?? ?? ?? ?if(lx[i]+ly[j] == edge[i][j]) map[i][j] = true; ? ?? ?? ?? ?else map[i][j] = false; ? ?? ?? ?} ? ?? ?} ? ?? ?// 匹配過程 ? ?? ?int live = 0; ? ?? ?memset(match, -1, sizeof(match)); ? ?? ?for(i = 0; i < n; i++) { ? ?? ?? ?memset(xckd, false, sizeof(xckd)); ? ?? ?? ?memset(yckd, false, sizeof(yckd)); ? ?? ?? ?if(DFS(i, n)) live++; ? ?? ?? ?else { ? ?? ?? ?? ?xckd[i] = true; ? ?? ?? ?? ?break; ? ?? ?? ?} ? ?? ?} ? ?? ?if(live == n) perfect = true; ? ?? ?else { ? ?? ?? ?// 修改標(biāo)號過程 ? ?? ?? ?int ex = INF; ? ?? ?? ?for(i = 0; i < n; i++) { ? ?? ?? ?? ?for(j = 0; xckd[i] && j < n; j++) { ? ?? ?? ?? ?? ?if(!yckd[j]) ex = min(ex, lx[i]+ly[j]-edge[i][j]); ? ?? ?? ?? ?} ? ?? ?? ?} ? ?? ?? ?for(i = 0; i < n; i++) { ? ?? ?? ?? ?if(xckd[i]) lx[i] -= ex; ? ?? ?? ?? ?if(yckd[i]) ly[i] += ex; ? ?? ?? ?} ? ?? ?} ? ?} } // 此函數(shù)用來尋找是否有以Xp為起點(diǎn)的增廣路徑，返回值為是否含有增廣路 bool DFS(int p, const int n) { ? ?int i; ? ?for(i = 0; i < n; i++) { ? ?? ?if(!yckd[i] && map[p][i]) { ? ?? ?? ?yckd[i] = true; ? ?? ?? ?int t = match[i]; ? ?? ?? ?match[i] = p; ? ?? ?? ?if(t == -1 || DFS(t, n)) { ? ?? ?? ?? ?return true; ? ?? ?? ?} ? ?? ?? ?match[i] = t; ? ?? ?? ?if(t != -1) xckd[t] = true; ? ?? ?} ? ?} ? ?return false; } int main() { ? ?int n, edge[size][size]; //? edge[i][j]為連接Xi與Yj的邊的權(quán)值 ? ?int i; ? ? ? ?/*************************************************** ? ? *? ? ? ?在此處要做的工作 : ? ? *? ? ? ?讀取二分圖每兩點(diǎn)間邊的權(quán)并保存在edge[][]中, ? ? *? 若X與Y數(shù)目不等，應(yīng)添加配合的頂點(diǎn) ? ? *? ? ? ?保存二分圖中X與Y的頂點(diǎn)數(shù)n,若上一步不等應(yīng)保 ? ? *? 存添加頂點(diǎn)完畢后的n ? ? ***************************************************/ ? ? ? ?KM_Perfect_Match(n, edge); ? ?int cost = 0; ? ?for(i = 0; i < n; i++) { ? ?? ?cost += edge[match[i]][i]; ? ?} ? ?// cost 為最大匹配的總和, match[]中保存匹配信息 ? ? ? ?return 0; } 17