吳永輝-圖論應(yīng)用-數(shù)模講座77

圖論應(yīng)用2004數(shù)學(xué)建模競(jìng)賽輔導(dǎo)復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系吳永輝博士2004年7月12日基礎(chǔ)知識(shí)離散數(shù)學(xué)（圖論）程序設(shè)計(jì)語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)與分析主要參考書(shū)目1周詠基,王建德.金牌之路——競(jìng)賽解題指導(dǎo).陜西師范大學(xué)出版社.2001.2吳文虎,王建德.實(shí)用算法的分析與程序設(shè)計(jì).電子工業(yè)出版社.1998.3吳文虎,王建德.圖論的算法與程序設(shè)計(jì).清華大學(xué)出版社.1997.4朱洪等.離散數(shù)學(xué)教程.上海科技文獻(xiàn)出版社.1966.5雷功炎.數(shù)學(xué)模型講義.北京大學(xué)出版社.2000.6ThomasH.Coremen,etc.IntroductiontoAlgorithm（算法導(dǎo)論）.高等教育出版社，TheMITPress.20027KennethH.Rosen.DiscreteMathematicsanditsApplications（離散數(shù)學(xué)及其應(yīng)用）.(4thEdition).2002.機(jī)械工業(yè)出版社,McGraw-Hill.(中、英文版)8Bela

Bollobas.ModernGraphTheory(現(xiàn)代圖論).科學(xué)出版社&Springer.2001圖論綜述1圖的基本概念圖的基本概念、路與回路、歐拉圖、哈密頓圖、最短路2平面圖平面圖與歐拉公式3圖的著色頂點(diǎn)著色、平面圖的著色、邊的著色4樹(shù)樹(shù)的性質(zhì)、生成樹(shù)與割集、樹(shù)的計(jì)數(shù)、有根樹(shù)與二分樹(shù)、最優(yōu)樹(shù)5網(wǎng)絡(luò)流連通度與塊、網(wǎng)絡(luò)最大流、圖與二分圖的匹配、獨(dú)立集和覆蓋、Petri網(wǎng)對(duì)應(yīng)策略將問(wèn)題A對(duì)應(yīng)另一個(gè)便于思考或有求解方法的問(wèn)題B，化繁為簡(jiǎn)，變未知為已知。將現(xiàn)實(shí)生活中問(wèn)題轉(zhuǎn)化為圖問(wèn)題1）經(jīng)典圖論問(wèn)題解析2）圖論問(wèn)題解析一、經(jīng)典圖論問(wèn)題解析將現(xiàn)實(shí)生活中問(wèn)題轉(zhuǎn)化為圖問(wèn)題的經(jīng)典問(wèn)題：1中國(guó)郵遞員問(wèn)題24

4的黑白格棋盤(pán)跳馬3

過(guò)河問(wèn)題1中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題（中國(guó)數(shù)學(xué)家管梅谷）背景：一個(gè)郵遞員從郵局出發(fā)投遞信件，他必須在所管轄范圍內(nèi)的所有街道至少走一次，最后回到郵局。

問(wèn)題：選擇一條最短的路線完成投遞任務(wù)。1）建立數(shù)學(xué)模型用圖描述問(wèn)題

G=(V,E,

)為一邊帶權(quán)的圖。

V中元素為街道交叉點(diǎn)；

E為街道集合；街道的長(zhǎng)度為街道對(duì)應(yīng)邊的權(quán)，顯然所有權(quán)均大于0。2）問(wèn)題分析如何選擇路線？

設(shè)G=(V,E,

)為一邊帶權(quán)的圖，所有權(quán)都非負(fù)。郵遞員問(wèn)題就轉(zhuǎn)化為：在G中，從某點(diǎn)v出發(fā)求一條經(jīng)過(guò)每條邊至少一次的閉路徑，使該閉路徑所帶的權(quán)最小。滿足條件的閉路徑稱(chēng)為最優(yōu)投遞路線3）算法分析（解決問(wèn)題的方法）：圖論，分而治之

若G為歐拉圖，最優(yōu)投遞路線就是從指定頂點(diǎn)出發(fā)的一條歐拉回路。

若G不是歐拉圖，則最優(yōu)投遞路線必須要有重復(fù)邊出現(xiàn)，而要求重復(fù)邊權(quán)之和達(dá)到最小。

G必有奇頂點(diǎn)，為了消除奇頂點(diǎn)，必須加若干條重復(fù)邊，使得重復(fù)邊的權(quán)與原邊的權(quán)相同，設(shè)所得圖為G*，則最優(yōu)投遞路線等價(jià)于求G*的一條歐拉回路，使得重復(fù)邊權(quán)之和最小，其中F=E(G*)-E(G)。4）G不是歐拉圖的最優(yōu)投遞路線算法當(dāng)G中只有兩個(gè)奇頂點(diǎn)u,v時(shí)，可先用標(biāo)號(hào)法求出從u到v的最短路，然后將最短路上的邊連其權(quán)各重復(fù)一次，得歐拉圖，再走一條歐拉回路，就是G中的一條最優(yōu)投遞路線。

5）理論基礎(chǔ)定理1：

C是帶權(quán)無(wú)向連通圖G=(V,E,

)中的最優(yōu)投遞路線當(dāng)且僅當(dāng)對(duì)應(yīng)的歐拉圖G*應(yīng)滿足：(1)G的每條邊在G*中至多重復(fù)出現(xiàn)一次；(2)G的每個(gè)圈在G*中重復(fù)出現(xiàn)的邊的權(quán)之和不超過(guò)該圈權(quán)的一半。證明：必要性（1）設(shè)C是最優(yōu)投遞路線，即C是G*中的歐拉回路，滿足

w(e)最小，F(xiàn)=E(G*)-E(G)。設(shè)G中邊e在G*中重復(fù)度為m(e)，即在G中的e的兩個(gè)端點(diǎn)u,v之間添加了m(e)-1條重復(fù)邊，若m(e)3，在G*中u,v之間的邊中隨便刪除兩條，不改變u,v度數(shù)的奇偶性，因而所得圖G**仍為歐拉圖，由于G中各邊的權(quán)均為正，因而W(F2)<W(F1)，其中F2=E(G**)-E(G)，而F1=E(G*)-E(G)，這與C是最優(yōu)投遞路線矛盾。定理2：設(shè)帶權(quán)無(wú)向連通圖G=(V,E,W)，V’為G中奇度頂點(diǎn)集，設(shè)|V’|=2k(k0)，F(xiàn)={e

|eE

在求G的最優(yōu)回路時(shí)加了重復(fù)邊

}，則F的導(dǎo)出子圖G[F]可以表示為以V’中頂點(diǎn)為起點(diǎn)與終點(diǎn)的k條不交的最短路徑之并。6）算法步驟：（J.Edmonds和E.L.Johnson70年代,O(n4)）1）若G中無(wú)奇頂點(diǎn)，令G*=G，轉(zhuǎn)2，否則轉(zhuǎn)3。2）求G*中的歐拉回路，結(jié)束。3）求G中所有奇度頂點(diǎn)對(duì)之間的最短路徑。4）以G中奇度頂點(diǎn)集V’為頂點(diǎn)集，

vi,vjV’，邊(vi,vj)的權(quán)為vi,vj之間最短路徑的權(quán)，得完全帶權(quán)圖K2k(2k=|V’|)。5）求中K2k最小權(quán)完美匹配M。6）將M中邊對(duì)應(yīng)的各最短路徑中的邊均在G中加重復(fù)邊，得歐拉圖G*，轉(zhuǎn)2。24

4的黑白格棋盤(pán)跳馬在4

4的黑白格棋盤(pán)（四分之一國(guó)際象棋盤(pán)）上跳馬，使得它經(jīng)過(guò)每個(gè)格一次并且僅一次，最后又回到出發(fā)點(diǎn)。能否辦到？為什么？1）構(gòu)造數(shù)學(xué)模型：將棋盤(pán)轉(zhuǎn)化為無(wú)向圖，作無(wú)向圖G=(V,E)。16個(gè)格中各放一個(gè)頂點(diǎn)頂點(diǎn)集V。馬跳“日”字，若馬能在vi和vj之間走一步，則vi和vj相鄰，于是就組成了邊集。2）算法思想：

G中是否存在哈密頓回路。定理（必要條件）若圖G是哈密頓圖，則對(duì)于頂點(diǎn)集V的每一個(gè)非空真子集S，均成立

(G-S)|S|

其中|S|表示S中的頂點(diǎn)數(shù)，G-S表示G中刪去頂點(diǎn)子集S后得到的圖。3）解：刪除中心四個(gè)點(diǎn)，得6個(gè)連通分支，由上述定理，圖中不存在哈密頓回路，所以無(wú)解。在88的黑白格棋盤(pán)（國(guó)際象棋盤(pán)）上跳馬，使得它經(jīng)過(guò)每個(gè)格一次并且僅一次，能最后又回到出發(fā)點(diǎn)。3

過(guò)河問(wèn)題一個(gè)人帶了一只狼、一只羊和一棵白菜過(guò)河。河邊有一條小船，每次除了人以外，只能帶一樣?xùn)|西。如果人不在，狼要吃羊，羊要吃白菜。1）構(gòu)造數(shù)學(xué)模型變量表示：M代表人，W代表狼，S代表羊，V代表白菜，

為空集。左岸初始情況：MWSV左岸可能出現(xiàn)的16情況：

MWSV,MWS,MWV,MSV,WSV,MW,MS,MV,WS,WV,SV,M,W,S,V,

其中不能出現(xiàn)的6情況：

MWV,MW,MV,WS,SV，M,構(gòu)造圖G(V,E)，V中頂點(diǎn)表示剩下的10中情況，如果經(jīng)過(guò)一次渡河，情況甲變成情況乙，在情況甲和情況乙表示的頂點(diǎn)間加一條邊，作為E中的邊。2）算法分析在圖G(V,E)中找一條從MWSV到

的最短路。3）解：7次擺渡MWSV

WV

MWV

V

W

S

MS

MWSV

WV

MWV

W

MSW

S

MS

二、圖論問(wèn)題解析1項(xiàng)鏈——?dú)W拉圖2旅館經(jīng)營(yíng)——網(wǎng)絡(luò)流3圖的著色3.1考試安排——頂點(diǎn)著色3.2時(shí)間表——邊著色4舞會(huì)——二分圖匹配5正方體著色——圖的基本概念6關(guān)鍵路徑練習(xí)1項(xiàng)鏈有一條用彩色珠子做的漂亮項(xiàng)鏈。每個(gè)珠子由兩種顏色組成，相繼的兩個(gè)珠子在鄰接處共享一種顏色：--(green|red)(red|white)(white|green)(green|blue)--

有一天，項(xiàng)鏈線斷了，珠子撒了一地。收集了地上的珠子，但無(wú)法肯定是否收齊。想知道用目前收集的珠子是否能夠聯(lián)成項(xiàng)鏈。數(shù)據(jù)實(shí)例1輸入51223344556輸出Somebeadsmaybelost數(shù)據(jù)實(shí)例2輸入輸出521211322343442312224建立數(shù)學(xué)模型：圖的模型關(guān)鍵問(wèn)題：什么為頂點(diǎn)？什么為邊？1)珠子為頂點(diǎn)，珠子串接的可能為邊無(wú)法將問(wèn)題的內(nèi)容表達(dá)完全如實(shí)例2,在圖中可以遍歷(1,2)–(2,3)–(2,2),得到的項(xiàng)鏈不符合題意.2)作G=(V,E)，每種顏色對(duì)應(yīng)一個(gè)頂點(diǎn)，V={v1,v2,……,vm}，每顆珠子對(duì)應(yīng)一條邊，若有珠子(c1,c2),就有無(wú)向邊vc1,vc2。

找歐拉回路練習(xí)2旅館經(jīng)營(yíng)問(wèn)題描述：

Praha是一座美麗的旅游城市，每年假期都有許多游客來(lái)Praha度假，HotelUVeze坐落在Praha郊區(qū)，有R間客房。假期將要來(lái)臨，賓館收到許多旅游公司的客房訂單，但畢竟賓館客房數(shù)有限，不能容納所有的游客?，F(xiàn)在假設(shè)你是HotelUVeze的經(jīng)理，請(qǐng)你有選擇地接受一部分訂單，使HotelUVeze可以從這些訂單中得到最大的收益。每份訂單給出它的起止時(shí)間和預(yù)定房間數(shù)。一旦接受某份訂單，在訂單規(guī)定的時(shí)間內(nèi)，就必須給旅客提供房間。

輸入輸出格式輸入：第一行為假期的總天數(shù)n和客房總數(shù)R，第2行到第n行是一個(gè)鄰接矩陣的上三角（不含對(duì)角線），cij表示第i天開(kāi)房，第j天退房的訂單預(yù)定的房間總數(shù)。輸出：輸出總收益天數(shù)m；接下來(lái)的m-1行中有一個(gè)鄰接矩陣的上三角（不含對(duì)角線），每個(gè)元素fij表示對(duì)預(yù)定日期為第i天開(kāi)房，第j天退房的訂單接受的房間總數(shù)。輸入輸出樣例輸入輸出12212000010000000000100000000000000000000000000000000000000000000000000000000000001000000000000002000001000000000000000010001000000建立數(shù)學(xué)模型：網(wǎng)絡(luò)流解題構(gòu)造一個(gè)能準(zhǔn)確描述問(wèn)題原型、又便于用標(biāo)準(zhǔn)算法求解的網(wǎng)絡(luò)模型。用網(wǎng)絡(luò)流解題。數(shù)學(xué)模型構(gòu)造圖G(V,E)。第i天對(duì)應(yīng)頂點(diǎn)i。頂點(diǎn)i到頂點(diǎn)i+1存在有向邊e(i=1,2,……,n-1)，e的流量上限c(e)=+

，費(fèi)用

(e)=0。若第i天開(kāi)房，第j天退房的訂單預(yù)定的房間總數(shù)為cij,且cij>0，則頂點(diǎn)i到頂點(diǎn)j存在有向邊e，e的流量上限c(e)=cij,費(fèi)用

(e)=-(j-i)，即天數(shù)的相反數(shù)。算法分析一個(gè)流量代表一份訂單，一個(gè)流的費(fèi)用為相應(yīng)訂單的收益天數(shù)的相反數(shù)，f個(gè)流的費(fèi)用為相同起訖日期的訂單之總收益天數(shù)的相反數(shù)。另一方面，房間數(shù)為R，故總流量不得超過(guò)R。所以要獲得最大收益，就要求G的流量為R的最小費(fèi)用流。最小費(fèi)用最大流方法練習(xí)3圖的著色3.1考試安排——頂點(diǎn)著色3.2時(shí)間表——邊著色3.1考試安排設(shè)學(xué)校共有n門(mén)課程要進(jìn)行期終考試,因?yàn)椴簧偻瑢W(xué)不止選修一門(mén)課,所以不能把一個(gè)同學(xué)選修的兩門(mén)課安排在同一場(chǎng)次進(jìn)行考試.問(wèn)學(xué)期的期終考試最少需要多少場(chǎng)次才能完成?構(gòu)造數(shù)學(xué)模型:圖的頂點(diǎn)著色設(shè)G=(V,E),以每門(mén)課程為一個(gè)頂點(diǎn)，當(dāng)且僅當(dāng)兩門(mén)課被同一個(gè)學(xué)生選修時(shí)，在相應(yīng)兩個(gè)頂點(diǎn)之間連一條邊。得圖G。

將n門(mén)功課劃分成K個(gè)劃分U1,U2,…,Uk,每個(gè)Ui(1ik)中頂點(diǎn)兩兩不相鄰，要求劃分?jǐn)?shù)K必須最少。算法分析：對(duì)每一個(gè)子集內(nèi)的頂點(diǎn)上同一顏色，同色頂點(diǎn)對(duì)應(yīng)的課程可以同時(shí)考試。同色頂點(diǎn)集是一個(gè)獨(dú)立集算法步驟：（1）求圖的所有極大獨(dú)立集（2）求出一切若干極大獨(dú)立集的和含所有頂點(diǎn)的方案（3）從中挑選所用極大獨(dú)立集個(gè)數(shù)最小者貪心3.2時(shí)間表學(xué)校有m位教師，X1,X2,……,Xm和n個(gè)班級(jí)Y1,Y2,……,Yn,Xi老師為Yj班每天上課，排一個(gè)課程表，使所排課時(shí)數(shù)目盡可能地少。構(gòu)造數(shù)學(xué)模型：令頂點(diǎn)集X={X1,X2,……,Xm}，Y={Y1,Y2,……,Yn}，頂點(diǎn)Xi和Yj之間有邊Pij相連當(dāng)且僅當(dāng)Xi老師為Yj班上一個(gè)課時(shí)的課。

形成一個(gè)二分圖每一學(xué)時(shí)，教師最多為一個(gè)班上課，每個(gè)班至多接受一個(gè)教師授課。

二分圖用盡可能少的顏色對(duì)邊著色，相鄰邊顏色不同理論基礎(chǔ)定理如果G是二分圖，則x’(G)=(G)。（邊色數(shù)=頂點(diǎn)最大度數(shù)）練習(xí)4舞會(huì)一次舞會(huì)，共有n位男士和n位女士參加，已知每位男士至少認(rèn)識(shí)兩位女士，而每位女士至多認(rèn)識(shí)兩位男士。問(wèn)能否將男士和女士分配為n對(duì)，使每對(duì)中男士和女士彼此認(rèn)識(shí)？1）構(gòu)造數(shù)學(xué)模型：二分圖n位男士和n位女士分別用頂點(diǎn)表示；若某位男士與某位女士認(rèn)識(shí)，在代表他們的頂點(diǎn)之間連一條線。定理：設(shè)G=(V1,V2,E)是二分圖，如果（1）V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t條邊；（2）V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊；則G中存在V1到V2的匹配，其中t是正整數(shù)。所以，可分配。練習(xí)5正方體著色有4個(gè)立方體，用紅、黃、藍(lán)、綠4種顏色將它們面著色，使得4種顏色在每個(gè)立方體的6個(gè)面中都至少出現(xiàn)1次。著色方案如下圖.證明：可將這4個(gè)立方體堆成四棱柱，使它每個(gè)側(cè)面都呈現(xiàn)4種顏色。

RRGBRYGB

RYBG

BBRY

GYRGRYG

Y

(1)(2)

(3)

(4)1）建立數(shù)學(xué)模型：用圖表示正方體的著色方式：

R(紅),Y(黃),B(藍(lán)),G(綠)表示4個(gè)頂點(diǎn);

頂點(diǎn)相鄰當(dāng)且僅當(dāng)正方體有兩個(gè)相對(duì)的面分別桌的是這兩種顏色；令Gi表示正方體i的著色方式，i=1,2,3,4；G=G1G2G3G4。2）算法分析存在可行方案的充要條件是G中存在兩個(gè)生成子圖，均含4條邊，且標(biāo)碼為1，2，3，4的邊各只出現(xiàn)一次，每個(gè)頂點(diǎn)關(guān)聯(lián)兩條邊。先按G調(diào)整好棱柱的前后兩個(gè)側(cè)面，使每個(gè)側(cè)面都具有不同的顏色，如下圖1所示；再按G調(diào)整左右兩個(gè)側(cè)面，前后側(cè)面顏色不變，使左右兩個(gè)側(cè)面的顏色如下圖2所示。前后左右

GRGYRBYBYGBRBYRG6關(guān)鍵路徑1）PERT

(ProgramEvaluationandReviewTechnique).計(jì)劃評(píng)審技術(shù),1956年。2）PERT圖設(shè)D是n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單帶權(quán)圖，若滿足：（1）D中無(wú)回路；（2）D中有一個(gè)頂點(diǎn)的入度為0，記為v1，稱(chēng)v1為發(fā)點(diǎn)，有一個(gè)頂點(diǎn)的出度為0，記為vn，稱(chēng)vn為收點(diǎn)；（3）任意的vV-{v1,vn}，則v在某條從v1到vn的路徑上，則稱(chēng)D是PERT圖。

在PERT圖中，每條邊表示一道工序或一種活動(dòng)，若有向邊(vi,vj),(vj,vk)相鄰，則表示工序(vj,vk)必須在(vi,vj)結(jié)束后才能開(kāi)始。

viV,vi表示一種狀態(tài)，它表示關(guān)聯(lián)到它的工序都結(jié)束后，關(guān)聯(lián)于它的工序才能開(kāi)始。

v1表示工程開(kāi)始

vn表示工程結(jié)束。3）關(guān)鍵狀態(tài)，關(guān)鍵工序/關(guān)鍵活動(dòng)在PERT圖中的關(guān)鍵路徑是從發(fā)點(diǎn)v1到收點(diǎn)vn的最長(zhǎng)（按權(quán)計(jì)算）的路徑。處于關(guān)鍵路徑上的頂點(diǎn)稱(chēng)為關(guān)鍵狀態(tài)，處在關(guān)鍵路徑上的邊稱(chēng)為關(guān)鍵工序或關(guān)鍵活動(dòng)。要使工期縮短，縮小關(guān)鍵路徑上邊的權(quán)。4）最早完成時(shí)間/最晚完成時(shí)間最早完成時(shí)間設(shè)PERT圖為有向圖D，任意的viV(D)，稱(chēng)從發(fā)點(diǎn)v1沿最長(zhǎng)的路到達(dá)vi所需要的時(shí)間為vi的最早完成時(shí)間，記作TE(vi)。

TE(vi)是以vi為起點(diǎn)的各工序的最早可能開(kāi)工時(shí)間，因而稱(chēng)為vi的最早完成時(shí)間，它是v1到達(dá)vi的最長(zhǎng)路徑的權(quán)。最晚完成時(shí)間在保證收點(diǎn)vn的最早完成時(shí)間TE(vn)不增加的條件下，從v1最遲到達(dá)vi所需要的時(shí)間，稱(chēng)為vi的最晚完成時(shí)間，記作TL(vi)。

TL(vi)為T(mén)E(vn)與vi沿最長(zhǎng)（按權(quán)計(jì)算）路徑到達(dá)vn所需時(shí)間之差，TL(vi)是關(guān)聯(lián)于vi的各道工序所允許的最遲開(kāi)工時(shí)間。5）緩沖時(shí)間/松弛時(shí)間

TL(vi)-TE(vi)為vi的緩沖時(shí)間或松弛時(shí)間，記為T(mén)S(vi)。

TS(vi)0，i=1,2,…,n.定理：

TS(vi)=0當(dāng)且僅當(dāng)vi處在關(guān)鍵路徑上。三、圖論難題思考1圖的基本概念（遍歷）拯救大兵瑞恩2網(wǎng)絡(luò)流標(biāo)號(hào)法航天實(shí)驗(yàn)家園1拯救大兵瑞恩問(wèn)題背景

1944年，特種兵麥克接到國(guó)防部的命令，要求立即趕赴太平洋上的一個(gè)孤島，營(yíng)救被敵軍俘虜?shù)拇蟊鸲?。瑞恩被關(guān)押在一個(gè)迷宮里，迷宮地形復(fù)雜，但是幸好麥克得到了迷宮的地形圖。迷宮的外形是一個(gè)長(zhǎng)方形，其在南北方向被劃分為N行，在東西方向被劃分為M列，于是整個(gè)迷宮被劃分為N*M個(gè)單元。我們用一個(gè)有序數(shù)對(duì)（單元的行號(hào)，單元的列號(hào)）來(lái)表示單元位置。南北或東西方向相鄰的兩個(gè)單元之間可以互通，或者存在一扇鎖著的門(mén)，又或者存在一堵不可逾越的墻。迷宮中有一些單元存放著鑰匙，并且所有的門(mén)被分為P類(lèi)，打開(kāi)同一類(lèi)的門(mén)的鑰匙相同，打開(kāi)不同類(lèi)的門(mén)的鑰匙不同。大兵瑞恩被關(guān)押在迷宮的東南角，即（N,M）單元里，并已經(jīng)昏迷。迷宮只有一個(gè)入口，在西北角，也就是說(shuō)，麥克可以直接進(jìn)入(1,1)單元。另外，麥克從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為1，拿取所在單元的鑰匙的時(shí)間以及用鑰匙開(kāi)門(mén)的時(shí)間忽略不計(jì)。你的任務(wù)是幫助麥克以最快的方式抵達(dá)瑞恩所在單元，營(yíng)救大兵瑞恩。

輸入輸出結(jié)構(gòu)輸入：第一行是三個(gè)整數(shù)，依次表示N,M,P的值；第二行是一個(gè)整數(shù)K，表示迷宮中門(mén)和墻的總個(gè)數(shù)；第I+2行（1<=I<=K），有5個(gè)整數(shù)，依次為Xi1,Yi1,Xi2,Yi2,Gi：當(dāng)Gi>=1時(shí)，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一扇第Gi類(lèi)的門(mén)，當(dāng)Gi=0時(shí)，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一堵不可逾越的墻；（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0<=Gi<=P）第K+3行是一個(gè)整數(shù)S，表示迷宮中存放的鑰匙總數(shù)；第K+3+J行(1<=J<=S)，有3個(gè)整數(shù)，依次為Xi1,Yi1,Qi：表示第J把鑰匙存放在(Xi1,Yi1)單元里，并且第J把鑰匙是用來(lái)開(kāi)啟第Qi類(lèi)門(mén)的。（其中1<=Qi<=P）注意：輸入數(shù)據(jù)中同一行各相鄰整數(shù)之間用一個(gè)空格分隔。輸出：輸出文件只包含一個(gè)整數(shù)T，表示麥克營(yíng)救到大兵瑞恩的最短時(shí)間的值，若不存在可行的營(yíng)救方案則輸出-1。

網(wǎng)絡(luò)流標(biāo)號(hào)法1航天實(shí)驗(yàn)2家園1航天實(shí)驗(yàn)