匹配應(yīng)用的實現(xiàn)數(shù)學(xué)建模

1、例題1 Place the Robots（ZOJ1654）問題描述 有一個N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。 Wall Grass Empty例題1 Place the Robots（ZOJ）模型一5467832112346578于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，

2、有沖突的空地間連邊，我們可以得到右邊的這個圖：例題1 Place the Robots（ZOJ）模型一5467832112346578在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：這是NP問題！我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。我們把這些塊編上號。同樣，把豎直方向的塊也編上號。例題1 Place the Robots（ZOJ）模型二123451234例題1 Place the Robo

3、ts（ZOJ）模型二123451234把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。于是，問題轉(zhuǎn)化成這樣的一個二部圖：112233445由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。例題1 Place the Robots（ZOJ）模型二123412354112233445比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型

4、中要素的選取有差異：模型一對要素的選取不充分，模型二則保留了原型中“棋盤”這個重要的性質(zhì)。由此可見，對要素的選取，是圖論建模中至關(guān)重要的一步。例題1 Place the Robots（ZOJ）小結(jié)例題2 救護傷員（TOJ1148）v無情的海嘯奪取了無數(shù)人的生命.很多的醫(yī)療隊被派往災(zāi)區(qū)拯救傷員.就在此時,醫(yī)療隊突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了,只剩下了N種。(1 n = 20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時，每天病人只能服用一種藥。也就是說，這些藥還夠支持N天?，F(xiàn)在，給出你每種藥在每天使用的效果，請你判斷當每種藥都用完后所有藥達到的效果之和最大可以是多少。 例題3

5、 打獵v獵人要在n*n的格子里打鳥，他可以在某一行中打一槍，這樣此行中的所有鳥都被打掉，也可以在某一列中打，這樣此列中的所有鳥都打掉。問至少打幾槍，才能打光所有的鳥？v建圖：二分圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。v該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。例題4 最小路徑覆蓋v一個不含圈的有向圖G中，G的一個路徑覆蓋是一個其結(jié)點不相交的路徑集合P，圖中的每一個結(jié)點僅包含于P中的某一條路徑。路徑可以從任意結(jié)點開始和結(jié)束，且長度也為任意值，包括0。請你求任意一個不含圈的有向圖G的最小路徑覆蓋數(shù)。v理清一個關(guān)系：最小路徑覆蓋數(shù)G的定點數(shù)最小路徑覆蓋中的邊數(shù)例題4 最小路徑覆蓋v試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。v拆點：將每一個頂點i拆成兩個頂點Xi和Yi。然后根據(jù)原圖中邊的信息，從X部往Y部引邊。所有邊的方向都是