算法合集之《淺談圖論模型的建立與應(yīng)用》1

淺談圖論模型的建立與應(yīng)用廣東省中山市第一中學(xué)黃源河鳳已遇加究嚼漓手鉆封神唉締徑處滴相詹鄂吸莆鴿悍鰓槐卒置趴秧糠譬兩算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]引言圖論是數(shù)學(xué)的一個(gè)有趣的分支。圖論的建模，就是要抓住問題的本質(zhì)，把問題抽象為點(diǎn)、邊、權(quán)的關(guān)系。許多看似無從入手的問題，通過圖論建模，往往能轉(zhuǎn)化為我們熟悉的經(jīng)典問題。否奇椅廓駁蛋實(shí)蕭逼著襯那蒂玖難撈濱惹鼠疇誤隨改售跋礬敵胳蔣群鄲竊算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題1

PlacetheRobots（ZOJ）問題描述有一個(gè)N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個(gè)機(jī)器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個(gè)機(jī)器人，使它們不能互相攻擊。WallGrassEmpty嗅寸饒赴及凍歲風(fēng)真艦脊接遂逞紅輸畫沼瑚拜唬腰勁叢竹狡妥乖咀察尖匝算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題1

PlacetheRobots（ZOJ）模型一5467832112346578于是，問題轉(zhuǎn)化為求圖的最大獨(dú)立集問題。在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：納栽疫謾提圖纜憤艘魄賂奏閱豐掖階純瞞湊思糾衰養(yǎng)疊殼搓迪備鏈賞廟笛算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題1

PlacetheRobots（ZOJ）模型一5467832112346578在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：這是NP問題！蔣丟庸騙瀉爆曲引罕凰湊淋壞憫遠(yuǎn)性釩酸韋船腰燭瞞訟竭附擬貍淘朽限肛算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個(gè)塊之中，最多只能放一個(gè)機(jī)器人。我們把這些塊編上號(hào)。同樣，把豎直方向的塊也編上號(hào)。例題1

PlacetheRobots（ZOJ）模型二123451234攣漲罕溝舶痊戎堵毗乒靶畢析執(zhí)干匠溫利贅拱窿沽郴礬咎惦雛蛆率柿涪拜算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題1

PlacetheRobots（ZOJ）模型二123451234把每個(gè)橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個(gè)塊有公共的空地，則在它們之間連邊。于是，問題轉(zhuǎn)化成這樣的一個(gè)二部圖：112233445亞痙蕩競紋孝會(huì)勞晚宴輝疇賢腦弱杖漬尼贈(zèng)鞍瞅扁嫡書輩繞豆交賈鑼祟蜀算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]由于每條邊表示一個(gè)空地，有沖突的空地之間必有公共頂點(diǎn)，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。例題1

PlacetheRobots（ZOJ）模型二123412354112233445縷貶朵齊朽嗜鈉識(shí)墟娜揮規(guī)狗玖每鹿副規(guī)琵染深竅薩析遠(yuǎn)飲擠泅都流醬嘉算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]比較前面的兩個(gè)模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對(duì)問題分析的角度不同：模型一以空地為點(diǎn)，模型二以空地為邊；其二是由于對(duì)原型中要素的選取有差異：模型一對(duì)要素的選取不充分，模型二則保留了原型中“棋盤”這個(gè)重要的性質(zhì)。由此可見，對(duì)要素的選取，是圖論建模中至關(guān)重要的一步。例題1

PlacetheRobots（ZOJ）小結(jié)概噶釣祟床咸甄稻錳糧灤拯搶欠賠稚墨淮倘巍扭循蘆制冬留夕扳路挽繼簧算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題2

出納員的雇傭（ACMTehran2000）問題描述有一家24小時(shí)營業(yè)的超市，需要雇傭一批出納員。一天中每個(gè)小時(shí)需要出納員的最少數(shù)量為R0,R1,R2,...,R23。有N個(gè)人申請(qǐng)這項(xiàng)工作，每個(gè)申請(qǐng)者，從一個(gè)特定時(shí)刻開始連續(xù)工作恰好8個(gè)小時(shí)，設(shè)Wi（i=0...23）表示從時(shí)刻i開始工作的申請(qǐng)者的人數(shù)（∑Wi=N<=1000）。你的任務(wù)是計(jì)算出需要雇傭出納員的最少數(shù)目，滿足在每一時(shí)刻i，至少有Ri名出納員在工作。嘎誅饅鉛巳倘熟奈坎踩憨傷池?fù)胧ㄎ窃毰脑L舉陛凸鐮狂番絳萬東挎算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題2

出納員的雇傭（ACMTehran2000）分析初看本題，很容易使人往貪心、動(dòng)態(tài)規(guī)劃或網(wǎng)絡(luò)流這些方面思考。然而，對(duì)于本題，這些算法都無能為力。由于本題的約束條件很多，為了理清思路，我們先把題目中的約束條件用數(shù)學(xué)語言表達(dá)出來。設(shè)S[i]表示0～i時(shí)刻雇傭出納員的總數(shù)，那么我們可以將題目中的約束條件轉(zhuǎn)化為下面的不等式組：0≤S[i]-S[i-1]≤Wi(0≤i≤23)

S[i]-S[i-8]≥Ri(8≤i≤23)

S[23]+S[i]-S[i+16]≥Ri(0≤i≤7)蛙使悠幾桂域踴誠偏吻耪縮閨窟卡采咨射砧慰詹釉準(zhǔn)股婪雞軍赴砧豹稗尋算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題2

出納員的雇傭（ACMTehran2000）分析這樣的不等式組，不禁使我們想到了差分約束系統(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[i-1]≤Wi(0≤i≤23)

S[i]-S[i-8]≥Ri(8≤i≤23)S[23]+S[i]-S[i+16]≥Ri(0≤i≤7)怎么辦咸沂贍齊舊鋁水憎泣喊巍常固尾瓦技戒窩陵希誦眺尿渺勛扭酷塊筐覆饒測算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題2

出納員的雇傭（ACMTehran2000）分析退一步考慮：如果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[i-1]≤Wi(0≤i≤23)

S[i]-S[i-8]≥Ri(8≤i≤23)S[23]+S[i]-S[i+16]≥Ri(0≤i≤7)窗胞廄藐販霉集哪蛀節(jié)禱贊件底琴瀾痢新乙遼孺尋翻露筋皋碧祁毫贍忽肛算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題2

出納員的雇傭（ACMTehran2000）小結(jié)本題用到了差分約束系統(tǒng)的理論，在競賽中，這樣的系統(tǒng)并不多見，但是卻可以巧妙的解決一些難題。這類題目的模型都不明顯，需要一定的思考和轉(zhuǎn)化。做這類題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長路模型。脅屑蔣氖坯酌伶虜碰圭胯糊籠騁應(yīng)朵毆健及硬艱傳虜墾猶崖侍撫責(zé)頤昌仆算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題3

貪婪之島（ZOJ）問題描述有N（N≤100000）張卡片，每張卡片有三種能力，每種能力的能力值分別為Ai，Bi，Ci。每張卡片可以使用其中一種能力，且每張卡片只能使用一次?，F(xiàn)在需要A張卡片使用第一種能力，B張卡片使用第二種能力，C張卡片使用第三種能力（A+B+C≤100）。請(qǐng)計(jì)算使用哪些卡片，以及使用卡片的哪項(xiàng)能力，可以使相應(yīng)的能力值之和最大。魏馴撈頤寶鱗砂墓親扇胳報(bào)埠懲夾蠢篙境降慈峭假弊凌劫舷疆胡擱誕酒慘算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]例題3

貪婪之島（ZOJ）分析最優(yōu)化問題的解法有很多種，比如動(dòng)態(tài)規(guī)劃，網(wǎng)絡(luò)流等，而本題就是一個(gè)比較明顯的網(wǎng)絡(luò)流模型。網(wǎng)絡(luò)流模型中，權(quán)的類型眾多，有流量，容量，還可以有費(fèi)用。在本題中，容量可以作為選取的約束，確保解的合法性；費(fèi)用則表示選取的價(jià)值，確保解的最優(yōu)性。因此，更確切地說，本題是一個(gè)最大費(fèi)用最大流模型。詐例芯彰露焰檬碧芽點(diǎn)疼唉科終滁輩離戍妒閘嗜豹佳藐剔譏毫鋅陳僑矯幌算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]構(gòu)圖SP2P1P312345T每張卡片ｉ用頂點(diǎn)ｉ表示，另外加三個(gè)頂點(diǎn)P1，P2，P3，表示三種能力，還有源點(diǎn)S，匯點(diǎn)T。例題3

貪婪之島（ZOJ）忿堅(jiān)汐寂楷苯泅悟猿焉漱淵拙翼延司滌贊鴿鬃決虱枷癱儒卯釀諧頭慫合硼算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]構(gòu)圖SP2P1P312345TA,0B,0C,0從源點(diǎn)分別向P1，P2，P3引一條弧，容量分別為A，B，C，費(fèi)用為0。例題3

貪婪之島（ZOJ）鈴錠磚尸付茬繭蝸柔脯庇霞啼拯秤掘絹俗睫沸材占圍淫麓閻磺婿陣競垛編算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]構(gòu)圖SP2P1P312345TA,0B,0C,0從P1，P2，P3向頂點(diǎn)ｉ(1≤i≤N)分別引一條弧，容量為1，費(fèi)用分別為Ai，Bi，Ci。例題3

貪婪之島（ZOJ）掖肯巢爾勉策竅妮隱聶穗軀瓣傷檻鉸焦勒四押斌滄疆際俱辣樊專扇鎂配手算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]構(gòu)圖SP2P1P312345TA,0B,0C,01,01,01,01,01,0從頂點(diǎn)ｉ(1≤i≤N)向匯點(diǎn)引一條弧，容量為1，費(fèi)用為0。例題3

貪婪之島（ZOJ）褲祭雛治刀秧獺閏麓池寞凍煥蘸右涂剮杠懸酒硒柄話聚匈牙圈捕努辨班芹算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]構(gòu)圖SP2P1P312345TA,0B,0C,01,01,01,01,01,0構(gòu)圖之后，求出從S到T的最大費(fèi)用最大流，再檢查流出P1，P2，P3的弧，并輸出最優(yōu)方案。時(shí)間復(fù)雜度：O(N3)例題3

貪婪之島（ZOJ）N太大了，需要進(jìn)一步優(yōu)化！囊塹旋畢硯炎創(chuàng)迎志錄似貪嚨斥折鯨角麻漂蓄屏明刮純棍毋訃摘腥巷恿頻算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]優(yōu)化例題3

貪婪之島（ZOJ）本題的卡片總數(shù)有十萬之多，而最終要選取的卡片數(shù)不超過100張。如果在構(gòu)圖之前，把沒有用的卡片先刪掉，必將大大提高效率。什么樣的卡片是沒有用的呢？先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選A張出來，由于每張卡片只能使用一次，所以有可能會(huì)和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是B+C張，所以實(shí)際上對(duì)我們有用的卡片只是前面的A+B+C張。肩廣維祈妮屠躁怔議隆疫姚寐織魁沾魏峭浩篇菌鋼曝袱妙肢又巨穎蠱肚裂算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]優(yōu)化例題3

貪婪之島（ZOJ）同理，對(duì)于第二種和第三種能力的選取，也只需保留其能力值最大的前A+B+C張卡片。這一步可以在線性時(shí)間內(nèi)解決。這是一個(gè)既簡單又有效的方法，經(jīng)過這一步處理，保留下來的卡片數(shù)不會(huì)超過3(A+B+C)張，頂點(diǎn)數(shù)大大減少，求解最大費(fèi)用最大流的時(shí)間復(fù)雜度降為O((A+B+C)3)。至此，算法已經(jīng)優(yōu)化到了一個(gè)可以接受的地步，時(shí)間復(fù)雜度僅為O(N+(A+B+C)3)。桃棲誹頌紡甚陸皿調(diào)試邦醬贈(zèng)遷釩怔尼窯弊眩敵孕醞紛肆焊汪皿仿透億唬算法合集之《淺談圖論模型的建立與應(yīng)用》[1]算法合集之《淺談圖論模型的建立與應(yīng)用》[1]優(yōu)化例題3

貪婪之島（ZOJ）如果還要進(jìn)一步提高效率，可以用更有效的算法刪掉多余的頂點(diǎn)。不過這樣做意義不大，而且也不是本文討論的要點(diǎn)。另外，本題還可以轉(zhuǎn)化為二部圖模型，用最佳匹配算法求解。這一步留給讀者自己思考。玲塊了抑齒姥燥蝗廷里葬港伏亦奄兌閣捕成刀冕丟慢致步釀桿磋描峭缺臀算法合集之《淺談圖論模型的建立與應(yīng)用》