國(guó)家集訓(xùn)隊(duì)2004論文集_黃源河.pdf

IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 1 頁(yè) 共 9 頁(yè) 淺談圖論模型的建立與應(yīng)用淺談圖論模型的建立與應(yīng)用 廣東省中山市第一中學(xué) 黃源河 關(guān)鍵字 圖論模型 建立 轉(zhuǎn)化 摘要 在近幾年的信息學(xué)競(jìng)賽中 圖論題目層出不窮 圖論作為 一個(gè)新生的數(shù)學(xué)分支 相比其他數(shù)學(xué)分支來(lái)說(shuō) 具有許多自有 的特性 利用圖論解題 通常具有高效 簡(jiǎn)潔的便利 有了這 門(mén)工具 并不意味就能很好地解決問(wèn)題 還在于我們能否熟練 地識(shí)別與建立一系列的圖論模型 本文通過(guò)一些實(shí)例 簡(jiǎn)單地 介紹一下圖論建模的方法 正文 引言引言 應(yīng)用數(shù)學(xué)知識(shí)解題時(shí) 首先要通過(guò)對(duì)實(shí)際問(wèn)題的分析 研究組建用以描述 這個(gè)問(wèn)題的數(shù)學(xué)模型 使用數(shù)學(xué)的理論和方法對(duì)模型進(jìn)行分析從而得到結(jié)果 再返回去解決現(xiàn)實(shí)的實(shí)際問(wèn)題 圖論模型是一類(lèi)特殊的數(shù)學(xué)模型 建立圖論模 型 就是要從問(wèn)題的原型中 抽取對(duì)我們有用的信息和要素 把問(wèn)題抽象為點(diǎn) 邊 權(quán)的關(guān)系 經(jīng)過(guò)圖論建模之后 雜亂無(wú)章的信息變得有規(guī)可尋 要素的內(nèi)在聯(lián)系體現(xiàn) 在了點(diǎn) 邊 權(quán)的關(guān)系 有不少經(jīng)典的圖論模型可以直接用特定的算法解決 一些復(fù)雜的問(wèn)題 只要能認(rèn)清問(wèn)題的本質(zhì) 把握問(wèn)題的關(guān)鍵 建立合適的圖論 模型 往往能轉(zhuǎn)化為我們熟悉的經(jīng)典問(wèn)題 本文要寫(xiě)的 正是我在圖論建模方面的一點(diǎn)心得與認(rèn)識(shí) IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 2 頁(yè) 共 9 頁(yè) 例題分析例題分析 例題 例題 1 Place the Robots ZOJ 問(wèn)題大意問(wèn)題大意 有一個(gè) N M N M 50 的棋盤(pán) 棋盤(pán)的每一 格是三種類(lèi)型之一 空地 草地 墻 機(jī)器人 只能放在空地上 在同一行或同一列的兩個(gè)機(jī) 器人 若它們之間沒(méi)有墻 則它們可以互相攻 擊 問(wèn)給定的棋盤(pán) 最多可以放置多少個(gè)機(jī)器 人 使它們不能互相攻擊 分析分析 在問(wèn)題的原型中 草地 墻這些信息不是我們所關(guān)心的 我們關(guān)心的只是 空地和空地之間的聯(lián)系 因此 我們很自然想到了下面這種簡(jiǎn)單的模型 以空地為頂點(diǎn) 有沖突的空地間連邊 我們可以得到下面的這個(gè)圖 那么 問(wèn)題轉(zhuǎn)化為求圖的最大獨(dú)立集問(wèn)題 眾所周知 這是 NP 完全問(wèn)題 看來(lái) 建立這樣的模型 沒(méi)有給問(wèn)題的求解帶來(lái)任何便利 我們必須建立一個(gè) 行之有效的新模型 我們將每一行 每一列被墻隔開(kāi) 且包含空地的區(qū)域稱(chēng)作 塊 顯然 在 每個(gè)塊之中 最多只能放一個(gè)機(jī)器人 我們把這些塊編上號(hào) 如下圖所示 54 6 7832 1 54 6 7832 1 12 34 6 5 7 8 12 34 6 5 7 8 1 32 5 4 1 2 3 4 1 2 3 4 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 3 頁(yè) 共 9 頁(yè) 把橫向塊作為 X 部的頂點(diǎn) 豎向塊作為 Y 部的頂點(diǎn) 如果兩個(gè)塊之間有公 共的空地 就在它們之間連邊 這樣 我們得到了下面的二部圖 1 1 2 2 3 3 4 4 51 1 2 2 3 3 4 4 5 由于每條邊表示一個(gè)空地 有沖突的空地之間必有公共頂點(diǎn) 所以問(wèn)題轉(zhuǎn) 化為二部圖的最大匹配問(wèn)題 這是圖論中的經(jīng)典問(wèn)題 可以用匈牙利算法解決 小結(jié)小結(jié) 比較上面的兩個(gè)模型 第一個(gè)過(guò)于簡(jiǎn)單 沒(méi)有認(rèn)清問(wèn)題的本質(zhì) 第二個(gè)則 充分抓住了問(wèn)題的內(nèi)在聯(lián)系 巧妙地建立了二部圖模型 為什么會(huì)產(chǎn)生這樣截 然不同的結(jié)果呢 其一是由于對(duì)問(wèn)題分析的角度不同 第一種模型以空地為點(diǎn) 第二種模型以空地為邊 其二是由于第一種模型對(duì)原型中信息的選取不足 所 建立的模型沒(méi)有保留原型中重要的性質(zhì) 而第二種模型則保留了原型中 棋盤(pán) 這個(gè)重要的性質(zhì) 由此可見(jiàn) 對(duì)信息的選取 是圖論建模中至關(guān)重要的一步 例題 例題 2 出納員的雇傭 出納員的雇傭 ACM Tehran 2000 問(wèn)題描述問(wèn)題描述 Tehran 的一家每天 24 小時(shí)營(yíng)業(yè)的超市 需要一批出納員來(lái)滿足它的需要 超市經(jīng)理雇傭你來(lái)幫他解決他的問(wèn)題 超市在每天的不同時(shí)段需要不同數(shù)目 的出納員 例如 午夜時(shí)只需一小批 而下午則需要很多 來(lái)為顧客提供優(yōu)質(zhì) 服務(wù) 他希望雇傭最少數(shù)目的出納員 經(jīng)理已經(jīng)提供你一天的每一小時(shí)需要出納員的最少數(shù)量 R0 R1 R23 R0 表示從午夜到上午 1 00 需要出納員的最少數(shù)目 R1表示上午 1 00 到 2 00 之間需要的 等等 每一天 這些數(shù)據(jù)都是相同的 有 N 人申請(qǐng)這項(xiàng)工作 每 個(gè)申請(qǐng)者 I 在沒(méi) 24 小時(shí)中 從一個(gè)特定的時(shí)刻開(kāi)始連續(xù)工作恰好 8 小時(shí) 定義 tI 0 tI 23 為上面提到的開(kāi)始時(shí)刻 也就是說(shuō) 如果第 I 個(gè)申請(qǐng)者被錄取 他 她 將從 tI 時(shí)刻開(kāi)始連續(xù)工作 8 小時(shí) 你將編寫(xiě)一個(gè)程序 輸入 RI I 0 23 和 tI I 1 N 它們都是非負(fù)整 數(shù) 計(jì)算為滿足上述限制需要雇傭的最少出納員數(shù)目 在每一時(shí)刻可以有比對(duì) 應(yīng)的 RI更多的出納員在工作 輸入輸入 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 4 頁(yè) 共 9 頁(yè) 輸入文件的第一行為測(cè)試點(diǎn)個(gè)數(shù) 20 每組測(cè)試數(shù)據(jù)的第一行為 24 個(gè) 整數(shù)表示 R0 R1 R23 RI 1000 接下來(lái)一行是 N 表示申請(qǐng)者數(shù)目 0 N 1000 接下來(lái)每行包含一個(gè)整數(shù) tI 0 tI 23 兩組測(cè)試數(shù)據(jù)之間沒(méi)有 空行 輸出輸出 對(duì)于每個(gè)測(cè)試點(diǎn) 輸出只有一行 包含一個(gè)整數(shù) 表示需要出納員的最少數(shù) 目 如果無(wú)解 你應(yīng)當(dāng)輸出 No Solution 分析分析 初看本題 很容易使人往貪心 動(dòng)態(tài)規(guī)劃或網(wǎng)絡(luò)流這些方面思考 但這些 算法對(duì)于本題都無(wú)能為力 由于本題的約束條件很多 為了理清思路 我們先把題目中的約束條件用 數(shù)學(xué)語(yǔ)言表達(dá)出來(lái) 設(shè) S i 表示 0 i 時(shí)刻雇傭出納員的總數(shù) Wi 表示在時(shí)刻 i 開(kāi)始工作的申請(qǐng)者的人數(shù) 那么我們可以將題目中的約束條件轉(zhuǎn)化為下面的不 等式組 7i0 R16 S i S i S 23 23i8 R 8 S i S i 23i0 W1 S i S i 0 i i i 這樣的不等式組 不禁使我們想到了差分約束系統(tǒng) 對(duì)于每條不等式 S i S j K 從頂點(diǎn) 向頂點(diǎn) i 引一條權(quán)值為 K 的有向邊 我們要求的 S 23 的最小 值 只要求頂點(diǎn) 0 到頂點(diǎn) 23 的最短路 但是注意上面第三條不等式 它包含三 個(gè)未知數(shù) 無(wú)法在圖中表示為邊的關(guān)系 思考到這一步 似乎陷入了僵局 難道本題不能用差分約束系統(tǒng)解決嗎 不 我們還需要一些轉(zhuǎn)化 退一步海闊天空 如果把 S 23 作為未知數(shù) 那是肯 定做不下去的 但是如果把 S 23 作為已知數(shù) 那么第三條不等式就只有兩個(gè)未 知數(shù) S i S i 16 我們從頂點(diǎn) i 16 向頂點(diǎn) i 0 i 7 引一條權(quán)值為 Ri S 23 的邊 那么 該不等式組可以完全轉(zhuǎn)化為一個(gè)有向圖 未知數(shù) S i 的解 就是圖中頂點(diǎn) 0 到頂點(diǎn) i 的最短路 而當(dāng)圖中存在負(fù)權(quán)回路時(shí) 不等式組無(wú)解 上面的解法是把 S 23 當(dāng)成了已知數(shù) 而實(shí)際上 S 23 不但是未知的 而且 正是我們要求的 怎么辦 我們可以用二分法枚舉 S 23 的值 逐步縮小范圍 用迭代法判斷是否存在負(fù)權(quán)回路 判定可行性 如果當(dāng) S 23 取到 N 仍不可行 則輸出 No Solution 否則輸出 S 23 的最小值 時(shí)間復(fù)雜度為 O 243 log2N 小結(jié)小結(jié) 本題用到了差分約束系統(tǒng)的理論 在競(jìng)賽中 這樣的系統(tǒng)并不多見(jiàn) 但是 卻可以巧妙的解決一些難題 這類(lèi)題目的模型都不明顯 需要一定的思考和轉(zhuǎn) 化 做這類(lèi)題目 關(guān)鍵是要把題目中的約束條件表示為不等式 再把不等式轉(zhuǎn) 化為圖的最短路或最長(zhǎng)路模型 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 5 頁(yè) 共 9 頁(yè) 例題 例題 3 貪婪之島貪婪之島 ZOJ 問(wèn)題大意問(wèn)題大意 有 N N 100000 張卡片 每張卡片有三種能力 每種能力的能力值分別 為 Ai Bi Ci 每張卡片可以使用其中一種能力 且每張卡片只能使用一次 現(xiàn)在需要 A張卡片使用第一種能力 B 張卡片使用第二種能力 C 張卡片使用第 三種能力 A B C 100 請(qǐng)計(jì)算使用哪些卡片 以及使用卡片的哪項(xiàng)能力 可以使相應(yīng)的能力值之和最大 分析分析 最優(yōu)化問(wèn)題的解法有很多種 比如動(dòng)態(tài)規(guī)劃 網(wǎng)絡(luò)流等 而本題就是一個(gè) 比較明顯的網(wǎng)絡(luò)流模型 網(wǎng)絡(luò)流模型中 權(quán)的類(lèi)型眾多 有流量 容量 還可以有費(fèi)用 在本題中 容量可以作為選取的約束 確保解的合法性 費(fèi)用則表示選取的價(jià)值 確保解 的最優(yōu)性 因此 更確切地說(shuō) 本題是一個(gè)最大費(fèi)用最大流模型 認(rèn)準(zhǔn)了問(wèn)題的模型之后 下一步就是構(gòu)圖了 l 每張卡片 i 用頂點(diǎn) i 表示 另外加三個(gè)頂點(diǎn) P1 P2 P3 表示三種能力 還有源點(diǎn) S 匯點(diǎn) T l 從源點(diǎn)分別向 P1 P2 P3引一條弧 容量分別為 A B C 費(fèi)用為 0 l 從 P1 P2 P3向頂點(diǎn) i 1 i N 分別引一條弧 容量為 1 費(fèi)用分別為 Ai Bi Ci l 從頂點(diǎn) i 1 i N 向匯點(diǎn)引一條弧 容量為 1 費(fèi)用為 0 S P2 P1 P3 1 2 3 4 5 T A 0 B 0 C 0 1 0 1 0 1 0 1 0 1 0 S S P2P2 P1P1 P3P3 1 1 2 2 3 3 4 4 5 5 T T A 0 B 0 C 0 1 0 1 0 1 0 1 0 1 0 構(gòu)圖之后 求出從 S 到 T 的最大費(fèi)用最大流 再檢查流出 P1 P2 P3 的弧 并輸出最優(yōu)方案 這樣的算法是十分粗糙的 時(shí)間復(fù)雜度為 O N3 空間復(fù)雜度 為 O N2 時(shí)空均不可行 需要進(jìn)一步優(yōu)化 本題的卡片總數(shù)有十萬(wàn)之多 而最終要選取的卡片數(shù)不超過(guò) 100 張 如果 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 6 頁(yè) 共 9 頁(yè) 在構(gòu)圖之前 把沒(méi)有用的卡片先刪掉 必將大大提高效率 什么樣的卡片是沒(méi)有用的呢 先考慮第一種能力的選取 如果把全部卡片按第一種能力值從大到小排序 顯然我們應(yīng)該盡量從前面選 A 張出來(lái) 由于每張卡片只能使用一次 所以有可 能會(huì)和其他的兩種能力發(fā)生沖突 而沖突的卡片數(shù)最多是 B C 張 所以實(shí)際上 對(duì)我們有用的卡片只是前面的 A B C 張 同理 對(duì)于第二種和第三種能力的選取 也只需保留其能力值最大的前 A B C 張卡片 這一步可以在線性時(shí)間內(nèi)解決 這是一個(gè)既簡(jiǎn)單又有效的方法 經(jīng)過(guò)這一步處理 保留下來(lái)的卡片數(shù)不會(huì) 超過(guò) 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 如果還要進(jìn)一步提高效率 可以用更有效的算法刪掉多余的頂點(diǎn) 不過(guò)這 樣做意義不大 而且也不是本文討論的要點(diǎn) 另外 本題還可以轉(zhuǎn)化為二部圖模型 用最佳匹配算法求解 這一步留給 讀者自己思考 小結(jié)小結(jié) 本題建立的是網(wǎng)絡(luò)流模型 這類(lèi)模型的算法系數(shù)大 編程復(fù)雜度也大 在 競(jìng)賽中往往作為走投無(wú)路時(shí)的 候補(bǔ)算法 但是 網(wǎng)絡(luò)流模型的適用性廣 一 些較復(fù)雜 或者約束較多的問(wèn)題 網(wǎng)絡(luò)流模型可以很好地解決 而基于網(wǎng)絡(luò)流 模型的問(wèn)題又比較明顯 這使得網(wǎng)絡(luò)流模型有著廣泛的應(yīng)用 總結(jié) 問(wèn)題是千變?nèi)f化的 如何建立問(wèn)題的圖論模型并沒(méi)有通用的準(zhǔn)則 前面的 幾個(gè)例子都比較簡(jiǎn)單 在更復(fù)雜的問(wèn)題中 有時(shí)我們會(huì)感到難以建立適當(dāng)?shù)哪?型 這時(shí) 我們需要在不改變問(wèn)題原型本身的性質(zhì)的前提下 對(duì)原型進(jìn)行抽象 簡(jiǎn)化 在此基礎(chǔ)上建立合適 有效的模型 有時(shí) 我們建立了問(wèn)題的一個(gè)模型 之后 可能會(huì)感到難以求解 這時(shí) 我們可能需要對(duì)模型進(jìn)行修改 轉(zhuǎn)化 或 者對(duì)原型進(jìn)行更深入的分析 抽取其中較關(guān)鍵的要素 建立一個(gè)易于求解的模 型 這些都需要我們有豐富的經(jīng)驗(yàn) 靈活的思維以及良好的創(chuàng)造力 參考文獻(xiàn) 1 吳文虎 王建德 實(shí)用算法的分析與程序設(shè)計(jì) 電子工業(yè)出版社 1998 2 吳文虎 王建德 青少年國(guó)際和全國(guó)信息學(xué) 計(jì)算機(jī) 奧林匹克競(jìng)賽指導(dǎo) 圖論的算法與程序設(shè)計(jì) 清華大學(xué)出版社 1997 3 IOI2003 國(guó)家集訓(xùn)隊(duì)第三階段討論稿 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 7 頁(yè) 共 9 頁(yè) 附錄 例題例題 1 原題原題 題目來(lái)源 題目來(lái)源 ZOJ Monthly October 2003 Contest Place the Robots Robert is a famous engineer One day he was given a task by his boss The background of the task was the following Given a map consisting of square blocks There were three kinds of blocks Wall Grass and Empty His boss wanted to place as many robots as possible in the map Each robot held a laser weapon which could shoot to four directions north east south west simultaneously A robot had to stay at the block where it was initially placed all the time and to keep firing all the time The laser beams certainly could pass the grid of Grass but could not pass the grid of Wall A robot could only be placed in an Empty block Surely the boss would not want to see one robot hurting another In other words two robots must not be placed in one line horizontally or vertically unless there is a Wall between them Now that you are such a smart programmer and one of Robert s best friends He is asking you to help him solving this problem That is given the description of a map compute the maximum number of robots that can be placed in the map Input The first line contains an integer T 11 which is the number of test cases For each test case the first line contains two integers m and n 1 m n 50 which are the row and column sizes of the map Then m lines follow each contains n characters of or o which represent Wall Grass and Empty respectively Output For each test case first output the case number in one line in the format Case id where id is the test case number counting from 1 In the second line just output the maximum number of robots that can be placed in that map Sample Input 2 4 4 IOI2004 國(guó)家集訓(xùn)隊(duì)論文 黃河源 第 8 頁(yè) 共 9 頁(yè) o oo o o 4 4 ooo o oo oo o Sample Output Case 1 3 Case 2 5 例題例題 3 原題 有改動(dòng) 原題 有改動(dòng) 題目來(lái)源 題目來(lái)源 ZOJ Sunny Cup 2003 Online Contest Greedy Island Gon and Killua are engaged in a game of Greedy Island The goal of the game is to collect 100 spell cards distributed all over the game A spell card has three properties Attack Defense and Special The numeric value of each property is between 0 and 100 Each card can be used only ONCE All the spell cards must be stored in the Book the initial item of the game The Book can store at most 50 spell cards so Gon and Killua can have at most 100 spell cards in all Now Gon and Killua have n spell cards and they want to use A cards for Attack B cards for Defense and C cards for Special uses A B C A B C they have to discard some cards They would like to know the maximum sum of the Attack value in Att