【正文】 Verifies, whether the machine described in the input file is well constructed,sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times. If there exists such an ordering of plates, your program should print thelarge number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word “acm” can be followed by the word “Motorola”. Your task is to write a puter program that will read the list of words and determine whether it is possible to arrange all of the plates in a end。 end。 for i:=1 to n do if d[i]0 then break。 procedure main。 if g[i]nil then g[i]^.prev:=nil。 g[i]:=g[i]^.next。 if t^.nextnil then t^.next^.prev:=t^.prev。 inc(d[ta])。 fillchar(rank,sizeof(rank),0)。 if ab then begin dec(bl)。 procedure merge(a,b:longint)。 t2^.f:=tb。 t2:=new(tnode)。{頂點數(shù)，邊數(shù)，基圖的極大連通子圖個數(shù)} g:array[1..maxn] of tnode。 print。 begin if not o then writeln(39。{原圖不連通，無解} for i:=1 to n do if odd(d[i]) then exit。 te:=te^.next。{以i為出發(fā)點尋找歐拉回路} var te:tnode。 for i:=1 to m do begin readln(ta,tb)。 procedure init。 ob:=b。 t2^.next:=g[tb]。 t1^.al:=false。{并查集中元素父結(jié)點和啟發(fā)函數(shù)值} list:array[1..maxm] of tnode。{邊的起始點和終止點} al:boolean。而問題的模型往往不是顯而易見的，我們必須在仔細分析、研究題目的基礎(chǔ)上，挖掘問題的本質(zhì)，拓展思路，大膽創(chuàng)新，才能建立合適的模型從而高效地解決問題。如果在DFS遍歷過程中，發(fā)現(xiàn)某個頂點存在一條回邊指向它的祖先結(jié)點，那么DFS樹中從到的路徑以及邊構(gòu)成一個回路?！　〖僭O(shè)某次游戲過程在圖中對應(yīng)的回路為。我們把這類圖稱為隨機歐拉圖。在開始游戲之前，你決定先編寫一個程序，判斷你能否獲勝。例題五　賭博機 題目來源：Polish Olympiad in Informatics 1996 Stage II Problem 3 Gambling，有改動題目描述　一臺賭博機由個整數(shù)發(fā)生器組成。具體來說，可以這樣構(gòu)造網(wǎng)絡(luò)：1 其頂點集為圖的所有頂點，以及附加的超級源和超級匯；2 對于圖中每一條邊，在中連邊，容量為，費用為該邊的長度；3 從源點向所有的頂點連邊，容量為，費用為0；4 從所有的頂點向匯點連邊，容量為，費用為0?！　》抡绽}三的思路，考慮能否通過在圖中增加若干條路徑得到歐拉圖，然后在中求歐拉回路?！　⊥暾乃惴鞒倘缦拢? 如果是連通圖，轉(zhuǎn)2，否則返回無解并結(jié)束；2 檢查中的奇點，構(gòu)成圖的頂點集；3 求出中每對奇點之間的最短路徑長度，作為圖對應(yīng)頂點間的邊權(quán)；4 對進行最小權(quán)匹配；5 把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖中得到圖；6 在中求歐拉回路，即所求的最優(yōu)路線。如果中奇點 度為奇數(shù)的頂點稱為奇點。這也說明歐拉回路應(yīng)用的靈活性。413165232356214564132456123465（圖中藍色格子為移動的起始位置，綠色格子為移動的終止位置。對任意，若，那么從向連條有向邊，表示商店多了個商品；若，那么從向連條有向邊，表示商店少了個商品。這樣，一共有個箱子，每家商店都將得到標簽為的箱子各一個。對于樣例我們可以按圖5所示的方式構(gòu)圖，圖中未表示出的頂點均為孤立點，可以事先將其刪去。數(shù)據(jù)規(guī)模　分析　通過對題目條件的一些初步分析，我們很容易得到下面的模型。如果圖是有向圖，我們?nèi)匀豢梢允褂靡陨纤惴?，只需將標記?/1的行刪去即可。 //1Eulercircuit ()。首先給出以下兩個性質(zhì)：性質(zhì)1　設(shè)是歐拉圖中的一個簡單回路，將中的邊從圖中刪去得到一個新的圖，則的每一個極大連通子圖都有一條歐拉回路。給圖加上一條虛擬邊得到圖，則圖的每一個頂點度均為偶數(shù)，故圖中存在歐拉回路。故是圖的歐拉回路。故圖中一定存在回路。設(shè)圖的一條歐拉回路為。歐拉圖　存在歐拉回路的圖稱為歐拉圖。經(jīng)過悉心研究，歐拉終于在1736年發(fā)表了論文《哥尼斯堡的七座橋》，不但成功地證明了“七橋問題”無解，而且找到了對于一般圖是否存在這類回路的充要條件。最后對歐拉回路的模型進行了總結(jié)，指出其特點和具備的優(yōu)勢?！娟P(guān)鍵詞】　　歐拉回路　歐拉路徑【正文】一　引言歐拉回路問題是圖論中最古老的問題之一。后人為了紀念歐拉這位偉大的數(shù)學家，便將這類回路稱為歐拉回路。半歐拉圖　存在歐拉路徑但不存在歐拉回路的圖稱為半歐拉圖。由于經(jīng)過圖的每一條邊，而圖沒有孤立點，所以也經(jīng)過圖的每一個頂點，為連通圖成立。設(shè)圖中邊數(shù)最多的一條簡單回路 邊沒有重復(fù)出現(xiàn)的回路稱為簡單回路。由定理1可以立即得到一個用于判定半歐拉圖的推論：推論1　無向圖為半歐拉圖，當且僅當為連通圖且除了兩個頂點的度為奇數(shù)之外，其它所有頂點的度為偶數(shù)。從中刪去得到一條從到的路徑，即為圖的歐拉路徑。證明　若為無向圖，則圖的各頂點的度為偶數(shù)；若為有向圖，則圖的各頂點的入度等于出度。將邊加入棧。以上介紹了歐拉回路的相關(guān)知識和算法。模型1：以個盤子作為頂點；如果盤子的末字母等于盤子的首字母，那么從向連一條有向邊。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一條邊的路徑，即歐拉路徑。倉庫是在一個狹窄的建筑里，所以箱子只好排成一列。　　例如，樣例，的情況，各個箱子的排列情況如下表：413165232356214564132455123466按上述方法構(gòu)造圖如下： 圖6 　　通過分析整個重排過程中空位的位置，不難發(fā)現(xiàn)：初始和結(jié)束狀態(tài)中，空位處于隊尾的位置；另外還可能有若干個中間狀態(tài)，空位也處于隊尾的位置。）　　現(xiàn)在問題轉(zhuǎn)化為：如何在圖中找出若干個沒有公共邊的回路，使得它們覆蓋圖中所有的邊。例題三　中國郵路問題（版本1） 題目來源：經(jīng)典問題題目描述　A城市的交通系統(tǒng)由若干個路口和街道組成，每條街道都連接著兩個路口。個數(shù)為2（設(shè)這兩個頂點為，），那么中一定存在一條從到的歐拉路徑。設(shè)圖中奇點個數(shù)為，那么一定能通過增加條路徑使得所有頂點的度為偶數(shù)。例題四　中國郵路問題（版本2） 題目來源：經(jīng)典問題題目描述　A城市的交通系統(tǒng)由若干個路口和街道組成，每條街道都連接著兩個路口?！　∈紫扔嬎忝總€頂點的入度與出度之差?！　⊥暾乃惴鞒倘缦拢? 如果的基圖連通且所有頂點的入、出度均不為0，轉(zhuǎn)2，否則返回無解并結(jié)束；2 計算所有頂點的值；3 構(gòu)造網(wǎng)絡(luò)；4 在網(wǎng)絡(luò)中求最小費用最大流；5 對中每一條流量的邊，在圖中增加次得到；6 在中求歐拉回路，即為所求的最優(yōu)路線。能夠產(chǎn)生的整數(shù)集合為，并且是集合的一個子集。如果能，程序?qū)⒏嬖V你每次如何選擇合適的數(shù)才能獲勝。顯然，隨機歐拉圖屬于歐拉圖。將回路經(jīng)過的邊從圖中刪去，得到殘留圖（即），那么中所有頂點的入度與出度相等。　　完整的算法流程如下： 建立有向圖； 判斷其中是否存在歐拉回路。【致謝】本論文的撰寫得到湖南師大附中李淑平老師的精心指導(dǎo)，在此表示衷心的感謝！同時感謝班上信息組同學和集訓(xùn)隊隊友的幫助與支持！【參考文獻】1 劉汝佳 黃亮　《算法藝術(shù)與信息學競賽》2 盧開澄 盧華明　《圖論及其應(yīng)用》3 戴一奇 胡冠章 陳衛(wèi)　《圖論與代數(shù)結(jié)構(gòu)》4 J. Edmonds, E.{訪問標記} rev,next:tnode。{最終找到的歐拉回路} o:boolean。 t1^.rev:=t2。 g[tb]:=t2。 while fa[b]b do b:=fa[b]。{初始化} var i,ta