【正文】 3121171415圖21樣例： 圖21中所示的平面圖最少需要8條路徑才能覆蓋所有的邊。因此解決這個問題只需要建立一個有容量下界的網(wǎng)絡(luò)，然后求這個網(wǎng)絡(luò)的最小可行流。然后在可行流上進(jìn)行修改，從匯點到源點求一個最大可行反向流，就得到了一個最小可行流。此算法實際效率很高，能夠迅速的通過測試數(shù)據(jù)。是否存在更好的模型描述此圖呢？為了更好的揭示問題的本質(zhì)，下面引入偏序集。符合這些特性的關(guān)系叫做偏序，通常用≤標(biāo)記R。含偏序≤的偏序集X用(X, ≤)表示。令a和b是偏序集(X, ≤)中的兩個元素。偏序集中的元素用平面上的點來表示。若偏序集中的兩個元素有a c b，那么對應(yīng)到圖中的兩個結(jié)點a和b，就有一條從b到a的有向邊(b, a)。反鏈?zhǔn)荅的一個子集A，在偏序關(guān)系≤下，它的每一對元素都是不可比的。令a、b為E中的兩個元素，設(shè)。直接計算鏈的個數(shù)似乎并不容易，好在有Dilworth定理揭示了鏈與反鏈的關(guān)系，從而使得問題的目標(biāo)進(jìn)一步轉(zhuǎn)化。根據(jù)Dilworth定理，問題轉(zhuǎn)化成求E中最長的反鏈的大小。如果用一條線將最長反鏈所對應(yīng)的邊從左到右連起來（如圖22所示），那么這條線不會與平面圖中的其它邊相交。圖22123459681013121171415極高點圖23極低點。若x在某個最長反鏈中，那么反鏈中和x相鄰且在x左邊的邊，只有可能在域F的左邊界上。每個結(jié)點的顏色用C[u]來記錄。 灰色while v是u后繼結(jié)點 do （按照從左到右的順序擴展u的后繼結(jié)點v）if C[v] 是白色then beginpre[v] 223。 pre[vh] (是黑色，說明是域的邊界上的結(jié)點；灰色就是極高點) 遞推求出右邊界的f(x) (pre回溯的邊是左邊界，是右邊界)pre[v] 223。因為原題給出的圖是平面圖，根據(jù)歐拉定理，邊數(shù)|E|和域數(shù)(或者說面數(shù))|F|都是O(n)級別的。正是由于回歸到問題的本質(zhì)，后面才能用DFS充分挖掘平面圖的性質(zhì)，得到最優(yōu)復(fù)雜度的算法。新題新作，應(yīng)該創(chuàng)新思路，深入分析問題的各種性質(zhì)，將這些性質(zhì)結(jié)合在一起，從而尋找到最能體現(xiàn)問題本質(zhì)的圖論模型。建立模型仿佛是為算法設(shè)計搭建一個平臺，接下來的工作是在這個平臺上充分挖掘和利用原題的性質(zhì)，設(shè)計一個解決問題的好算法。然后她在多邊形中畫了幾個不相交的對角線（公共點為頂點不算相交）。那么一個可能的頂點標(biāo)號順序為(1, 3, 5, 2, 4)。由此可知，在圖G中只存在惟一的一條哈密頓回路。問題的目標(biāo)就是要找到這個哈密頓回路。因此，得到算法一：算法一：1．枚舉圖中的每條邊(u, v)，進(jìn)行如下判斷：將u和v兩個頂點從圖G中刪除得到新圖G’。這時的新圖C便是圖G中的哈密頓回路，因此只要對其進(jìn)行一次遍歷就可以得到多邊形頂點的標(biāo)號序列了。 分而治之繼續(xù)挖掘圖G的性質(zhì)發(fā)現(xiàn)，由于圖G中的對角線是不相交的，那么必定存在一個頂點u，它的度數(shù)為2。由于圖中一定存在一個頂點u，它的度數(shù)為2。也就是說，可以把Hi從圖G中刪除，若Hi1 和Hi+1之間沒有邊相連，就添加一條新邊（Hi1,Hi+1）（虛邊），得到新圖G’。然后按照同樣的方法把Hj從圖G’刪除，得到一個新圖……。最后，圖C便是要求的原始多邊形。如何判斷從Hi+1到Hj1的頂點是否已經(jīng)被刪除呢？這時構(gòu)造的附加圖C就起到了作用！若從Hi+1到Hj1的頂點已經(jīng)被刪除，則這些頂點在原多邊形上相應(yīng)的邊都已經(jīng)添加到圖C中，Hi到Hj在圖C中一定存在一條路徑。還要用一個哈希表存下所有的邊，用于查找任意兩個點是否相連。由于頂點的度數(shù)只減少不增加，而且真正有效的度數(shù)只有1和2，所以可以建立四個桶來替代堆。在雙向鏈表中的插入和刪除結(jié)點，時間復(fù)雜度都是O(1)。添加一條邊和判斷一對點的連通性兩種操作的均攤復(fù)雜度為O(α(n))。3． 在鄰接表中找到和u相連的兩個頂點為v1和v2。5． 將頂點u標(biāo)記為不可用。然后轉(zhuǎn)到步驟2?，F(xiàn)在分析一下時間復(fù)雜度：步驟3中，每個頂點最多查找一次，因此復(fù)雜度為邊數(shù)，即O(n)；步驟4和步驟6中，用并查集查找和插入的均攤時間復(fù)雜度為O(nα(n))；步驟5中，用哈希表查找一條邊的復(fù)雜度為O(1)，邊的插入和桶的調(diào)整也是O(1)，一共進(jìn)行頂點數(shù)次，所以時間復(fù)雜度為O(n)。我們不禁提出一個問題：是否能找到一種綜合的方法，將所有特性一起利用，使得解決方法既簡便又高效呢？ DFS樹反映的問題特性回到多邊形所在的平面圖上。首先定義一下DFS中需要用到的兩個函數(shù)：dfn[v]表示v是深搜中第幾個被遍歷到的。根據(jù)v的度數(shù)分下面四種情況：uvw圖34yxuv圖331．v的兒子數(shù)為0：意味著(u,v)是原始多邊形的邊。v不是x的父親結(jié)點，說明x一定先于u被遍歷到，而且x是u的祖先結(jié)點。因此y一定后于x被遍歷，即dfn[y]小于dfn[x]。若low[w]大于等于dfn[u]，則(u, v)為多邊形的對角線。若low[w]小于dfn[u]，則(u, v)是多邊形的邊，而與v相連的另一條多邊形的邊可以在遍歷w時找到。所以算法三的時間復(fù)雜度為線性的——O(n)！ 小結(jié)上述三種方法都是建立在同一個模型上的，不同的方法對模型性質(zhì)挖掘的深度不同也就決定了不同的時間復(fù)雜度。由于每個子問題都解決了，原問題也就迎刃而解。三種不同的方法也給了我們不同的啟示：定義法告訴我們，當(dāng)找不到問題思考的方向時，可以考慮從問題最基本的性質(zhì)入手尋找突破口。建立模型要求我們熟悉經(jīng)典模型，同時又要求我們能夠勇于探索，大膽創(chuàng)新，敢于跳出經(jīng)典模型的框框。它們不僅僅是一種方法，更是一種思維的方式和思考的角度。優(yōu)化是為了進(jìn)一步的完善程序設(shè)計，是一種不斷進(jìn)取的精神。所謂萬變不離其宗，只有最基本的思想和方法才是解決問題的不二法門。當(dāng)n=1時，定理顯然成立。這樣直觀上的看，A?是所有A“下方”的元素組成，而A+是所有A“上方”的元素組成。因此A+≠P，A+中的元素個數(shù)小于P的元素個數(shù)n。因此性質(zhì)3成立。也就是說x和A中的所有元素都是不可比的，那么是一條比A更長的反鏈，這與A是P中最長的反鏈矛盾。類似地，設(shè)A?劃分成，且。ai是Ci+中結(jié)尾的那些元素，是Ci?開始的那些元素，將Ci+和Ci?接在一起形成了m條鏈，它們是P的一個劃分。根據(jù)歸納假設(shè)，可以被劃分成m – 1條鏈。有3種情形：1) a是某個域F1左邊界上的一條邊，那么F1右邊界上的一條邊c與a和b都是不可比的，那么是一條更長的反鏈，矛盾。由于平面圖中的最高點vh到u1和u2都至少存在一條路徑，因此這些路徑之間至少存在一個公共點既能夠到達(dá)u1也能夠到達(dá)u2，令這些公共點中縱坐標(biāo)最低的點為uh。因此反鏈中相鄰的兩條邊一定是在同一個域中。 writes the result to the text file . InputIn the first line of the input file there is one integer n equal to the number of clearings, 2=n=5…。writes the result.InputThe first line of the input contains exactly one positive integer d equal to the number of data sets,1 ≤ d ≤ 20. The data sets follow.Each data set consists of exactly two consecutive lines.The first of those lines contains exactly two integers n and m separated by a single