浙江大學(xué)Acm競賽常用算法與數(shù)據(jù)結(jié)構(gòu)

常用算法

&數(shù)據(jù)結(jié)構(gòu)浙江大學(xué)微軟技術(shù)俱樂部彭鵬ACM競賽12、競賽中常見的16種題型1、ACM/ICPC簡介4、競賽中基本的數(shù)據(jù)結(jié)構(gòu)與算法5、ZOJ入門3、時空復(fù)雜度的分析2ACMAssociationforComputingMachinery美國計(jì)算機(jī)學(xué)會ICPCInternationalCollegiateProgrammingContest國際大學(xué)生程序設(shè)計(jì)競賽ACM/ICPC簡介3ACMACM(AssociationforComputingMachinery)

成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最悠久、最具權(quán)威性的組織，是推進(jìn)信息技術(shù)專業(yè)人員和學(xué)生提高技巧的主要力量。ACM通過提供前沿技術(shù)信息和從理論到實(shí)踐的轉(zhuǎn)化，為其全球7.5萬名成員服務(wù)，并已經(jīng)成為信息科技領(lǐng)域的一個基本信息來源。

4ICPCACM主辦的國際大學(xué)生程序設(shè)計(jì)競賽(InternationalCollegiateProgrammingContest)，簡稱ACM/

ICPC，自從1977年開始至今已經(jīng)連續(xù)舉辦28屆。其宗旨是提供一個讓大學(xué)生向IT界展示自己分析問題和解決問題的能力的絕好機(jī)會，并成為一個有效的途徑，讓下一代IT天才可以接觸到其日后工作中將要用到的各種軟件。自1998年IBM成為該項(xiàng)競賽的贊助商以來，大賽規(guī)模不斷擴(kuò)大。去年有71個國家1582所大學(xué)派出4109支隊(duì)伍參加了30個賽點(diǎn)的分區(qū)賽，其中78支隊(duì)伍參加今年4月在上海香格里拉酒店舉辦的世界總決賽?，F(xiàn)在，ACM/ICPC已成為世界各國大學(xué)生中最具影響力的國際計(jì)算機(jī)賽事。

5ICPC競賽規(guī)則三人組隊(duì)在4~6小時編寫C/C++或Java程序解決6~10道題完成題目數(shù)多的隊(duì)伍優(yōu)勝完成題目數(shù)一樣的隊(duì)伍,罰時少的優(yōu)勝6ICPClogAproblemAthoughtAsolutionAballoon7中國各高校ACM開展情況清華大學(xué)上海交通大學(xué)中山大學(xué)復(fù)旦大學(xué)北京大學(xué)南京大學(xué)浙江大學(xué)8浙江大學(xué)ACM集訓(xùn)隊(duì)選拔標(biāo)準(zhǔn)根據(jù)校內(nèi)程序設(shè)計(jì)競賽的結(jié)果，現(xiàn)擬定集訓(xùn)隊(duì)具體選拔標(biāo)準(zhǔn)如下：1.曾參加過去年暑假集訓(xùn)的隊(duì)員自愿入圍；未參加過集訓(xùn)，但滿足下列條件者自愿入圍：2.對ACMICPC活動有極大熱情，視練習(xí)題如游戲；并且3.校內(nèi)程序設(shè)計(jì)競賽前5名；或者4.校內(nèi)程序設(shè)計(jì)競賽第6-9名，并且7月1日前在ZOJ通過至少100題；或者5.校內(nèi)程序設(shè)計(jì)競賽第10-15名，并且7月1日前在ZOJ通過至少150題；或者6.7月1日前在ZOJ通過至少200題。9如何建立一支強(qiáng)隊(duì)個人的能力理論(幾何,數(shù)論,動態(tài)規(guī)劃,圖論等)技術(shù)(編程)隊(duì)員能力上的互補(bǔ)某論壇，一無聊男yy的中國“夢之隊(duì)”錢文杰（？）反應(yīng)奇快，擅長隨機(jī)化，貪心，NOI貪心王劉汝佳or吳嘉之見多識廣，做過的題必別人見過的題多趙爽上海交大的“割題手”10Leader/Coordinato(協(xié)調(diào)比賽進(jìn)程)Reader(發(fā)現(xiàn)題目隱諱的涵義)Thinker(邏輯能力強(qiáng),收集其他隊(duì)員意見)Programmer/Debugger(反應(yīng)快/穩(wěn),細(xì)心)Helper(協(xié)助比賽,查錯,驗(yàn)證數(shù)據(jù)等)一支強(qiáng)隊(duì)需要的角色11參考書籍主要參考書籍《C++Primer》《C++標(biāo)準(zhǔn)程序庫》《算法導(dǎo)論》《算法藝術(shù)與信息學(xué)競賽》《組合數(shù)學(xué)》《計(jì)算幾何》？？歷屆國家集訓(xùn)隊(duì)論文12網(wǎng)絡(luò)資源http://acm.timus.ruhttp://acm.sgu.ru/usacogate/bbs/index.php13時空復(fù)雜度的分析時間復(fù)雜度的分析空間復(fù)雜度的分析14函數(shù)增長和運(yùn)行時間引用劉汝佳《序列和字符串》15常見題型DynamicProgramming(動態(tài)規(guī)劃)Greedy(貪心)

CompleteSearch(窮舉)

FloodFill(種子填充)16常見題型ShortestPath(最短路徑)RecursiveSearchTechniques(回溯）MinimumSpanningTree（最小生成樹）Knapsack（背包）17常見題型ComputationalGeometry(計(jì)算幾何)

NetworkFlow(網(wǎng)絡(luò)流)EulerianPath(歐拉回路)Two-DimensionalConvexHull(二維凸包)18常見題型BigNums(大數(shù))HeuristicSearch(啟發(fā)式搜索)ApproximateSearch(近似搜索)AdHocProblems(雜題)1920枚舉法

又叫窮舉法，它利用了計(jì)算機(jī)計(jì)算速度快且準(zhǔn)確的特點(diǎn)，是最為樸素和有效的一種算法。不是辦法的辦法但有時卻是最好的辦法21PizzaAnyone?（ZOJ1219）題目大意：你需要為你和你的朋友們訂一個皮薩。每個朋友都會告訴你他們想和不想放進(jìn)皮薩里的東西。你是否能訂一個皮薩，讓他滿足每個人至少一個條件。假設(shè)一共有16種東西可以放進(jìn)皮薩。22

是個對計(jì)算機(jī)很小的數(shù)23貪心法(Greedy)矩陣胚理論（詳情請參考算法導(dǎo)論）枚舉法的時間效率很低，貪心法恰恰與其相反。并且貪心法的程序也很好實(shí)現(xiàn)。無數(shù)論文都指責(zé)貪心法往往得不到問題的最優(yōu)解。絕世高手與普通高手的差距所在。24棧和隊(duì)列棧：后進(jìn)先出（LIFO）隊(duì)列：先進(jìn)先出（FIFO）25字符串的輸入與輸出

<cstring>或<string.h><string>chars[100];scanf("%s",s);stringa(s);Stringa;cin>>a;C++常用頭文件字符串的讀入哪種讀入更快？在輸入數(shù)據(jù)達(dá)到1M時，cin，cout將比scanf,printf在速度上有明顯的劣勢26排序排序的種類：交換排序，選擇排序，插入排序，堆排序希爾排序，快速排序，歸并排序，桶排序27用C++實(shí)現(xiàn)排序#include<algorithm>數(shù)組a sort(a,a+5);vectora sort(a.begin(),a.end());28并查集并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并問題。并查集的主要操作有1－合并兩個不相交集合2－判斷兩個元素是否屬于同一個集合3－路徑壓縮29Parity(ceoi99)有一個01序列,長度<=1000000000,現(xiàn)在有n條信息,每條信息的形式是－abeven/odd。表示第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù)。你的任務(wù)是對于這些給定的信息，輸出第一個不正確的信息所在位置-1。信息的數(shù)目不超過5000。如果信息全部正確，即可以找到一個滿足要求的01序列，那么輸出n。30Parity(ceoi99)從整個01序列肯定是無法入手的，因?yàn)樗拈L度高達(dá)109。從范圍比較小的n入手。也就是說我們需要對信息進(jìn)行一些特殊的處理。abeven/odd，那么將元素b指向a-1，邊的權(quán)值是even/odd。下面我們由樣例來說明一下這個處理方法。31Parity(ceoi99)（肖天）建立sum數(shù)組，sum[i]表示從1到i之和是奇（true）還是偶（false），sum[0]=false。這樣題目中給的任意問題（a,b）的答案都可以用sum[b]xorsum[a-1]表示。開始我們并不知道sum[1..n]的值，不妨設(shè)為false，這時任意sum[a],sum[b]都是獨(dú)立的。對于每對問答(a,b,c)，都可以知道sum[b]xorsum[a-1]=c,由此把sum[b]和sum[a-1]聯(lián)系起來。這步操作可以用并查集完成，對于問答（a,b,c）如果sum[a-1],sum[b]不屬于一個集合就把它們并起來，否則如果sum[a-1]xorsum[b]不等于c則說明出現(xiàn)矛盾，輸出總句數(shù)，退出。對于不出現(xiàn)矛盾的sum數(shù)組，對于每個集合分為兩個部分，我們指定其中一個部分為true，另一個部分為false，則可以確定sum數(shù)組，利用sum[i]xorsum[i-1]可以求出第i位的數(shù)字，由于不同集合之間沒有問答出現(xiàn)，所以此數(shù)列是一可行解，證明算法正確。32堆(優(yōu)先隊(duì)列)優(yōu)點(diǎn)：

實(shí)現(xiàn)簡單動態(tài)維護(hù)一組數(shù)據(jù)中最?。ù螅┑囊粋€數(shù)組維護(hù)<priority_queue>33例題:積水一個長方形網(wǎng)格包含了n*m塊地，每塊地上面有1個長方體。每一個長方形蓋住了一塊地，地的面積是1平方英寸。相鄰的地上的長方體之間沒有空隙。一場大雨降臨了這個建筑物，在建筑物的某些區(qū)域有積水產(chǎn)生。給各方格高度,求積水總量34分析定義每塊地上的長方體的高度稱為原始高度積滿水時的水面高度稱為積水高度（高于積水高度的水一定會流走，低于積水高度的水一定流不走）積水高度與原始高度之差為積水深度如果一個長方體上不可能有積水，那么它的積水高度就等于它的原始高度。最外圈不能積水，積水高度等于原始高度35分析由外而內(nèi)計(jì)算。每次選取外圍的格子中積水高度最低的一個格子x，考慮它周圍所有在網(wǎng)格內(nèi)部的格子y想象不斷的往x和y里注水，但是x的積水高度固定（想象該高度處有一個小孔），因此如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度每次用堆取出x進(jìn)行計(jì)算，O(mnlogmn)。36哈希表(Hash)理論上查找速度最快的數(shù)據(jù)結(jié)構(gòu)之一缺點(diǎn)： 需要大量的內(nèi)存 需要構(gòu)造Key

37Hash表的實(shí)現(xiàn)數(shù)組沖突解決法開散列法閉散列法C++sgistl實(shí)現(xiàn)38HashKey的選取數(shù)值：方法一：直接取余數(shù)（一般選取質(zhì)數(shù)M最為除數(shù)）方法二：平方取中法，即計(jì)算關(guān)鍵值的平方，再取中間r位形成一個大小為的表是多少？39字符串：intELFhash(char*key){ unsignedinth=0; while(*key){ h=(h<<4)+*key++; unsignedlongg=h&0Xf0000000L; if(g)h^=g>>24; h&=-g; } returnh%M;}方法二：ELFhash函數(shù)方法一：折疊法：即把所有字符的ASCII碼加起來40二分搜索樹普通的二分搜索樹時間復(fù)雜度：缺點(diǎn)：

容易出現(xiàn)不平衡的情況AVLTree，Splaytree,紅黑樹41樹堆(Treap)Treap=Tree+heap每次插入/刪除結(jié)點(diǎn)的時候，給結(jié)點(diǎn)隨機(jī)分配一個優(yōu)先級，讓Treap關(guān)于優(yōu)先級形成一個堆的同時，關(guān)于關(guān)鍵碼形成BST跳躍表、B樹42跳躍表（Skiplists）43線段樹在一類問題中，我們需要經(jīng)常處理可以映射在一個坐標(biāo)軸上的一些固定線段，例如說映射在OX軸上的線段。由于線段是可以互相覆蓋的，有時需要動態(tài)地取線段的并，例如取得并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。一個線段是對應(yīng)于一個區(qū)間的，因此線段樹也可以叫做區(qū)間樹。4445

Atlantis（ZOJ1128）一個平面被很多矩形覆蓋，矩形之間會相互疊加。輸出矩形覆蓋的總面積。46Atlantis（ZOJ1128）

線段樹矩形切割47矩形切割48字典樹(Trie) 當(dāng)關(guān)鍵字是串的時候，理論上查找最快的數(shù)據(jù)結(jié)構(gòu)定義：保存字符串用的樹型數(shù)據(jù)結(jié)構(gòu)(多叉樹），其中每個節(jié)點(diǎn)表示一個公共前綴，單詞信息保存在相應(yīng)的頁節(jié)點(diǎn)里面。49給如下幾個單詞，構(gòu)造的單詞樹：An，Ant，All，AllotAlloy，Aloe，Are，Atebe版權(quán)歸浙江大學(xué)ACM領(lǐng)隊(duì)徐串所有轉(zhuǎn)載需保留此字樣50T9（ZOJ1038）題目描述：手機(jī)有智能英文輸入法，他根據(jù)自己已有的詞匯表，即使你每個數(shù)字只按一次也可以猜出你要按的是哪個單詞（方法就是從所有可能的串中選出出現(xiàn)概率最高的一個）。詞匯表:hell3

hello4

idea8

next8

super3按435561是的響應(yīng)顯示i

id

hel

hell

hello51動態(tài)規(guī)劃動態(tài)規(guī)劃的時間效率極高。動態(tài)規(guī)劃的算法簡潔，一般只用邊界和狀態(tài)轉(zhuǎn)移方程就可清晰地表示出進(jìn)行規(guī)劃的步驟；而因?yàn)橛辛诉@些用數(shù)學(xué)語言描述的天然材料，編程也較為方便。最重要的一點(diǎn)：動態(tài)規(guī)劃不單是一種思想，也不單是一類算法，它是思想方法和具體算法的混合物。摘自徐靜《動態(tài)規(guī)劃的算法與實(shí)現(xiàn)》52動態(tài)規(guī)劃無后效性遞推法和記憶化搜索53深度優(yōu)先搜索(DFS)按照深度優(yōu)先的順序遍歷狀態(tài)空間，通常用遞歸或者棧來實(shí)現(xiàn)。voiddfs(state,depth){ if(state==結(jié)束狀態(tài)）退出； 枚舉所有可行狀態(tài){ 更新全局變量； dfs(newstate,depth+1); 還原全局變量 } }54寬度優(yōu)先搜索(BFS)如果代價和搜索樹深度成正比，那么可以通過廣度優(yōu)先搜索得到解。由于空間占用大，BFS用處不是很廣，一般只用在路徑尋找問題中，但是一旦使用，將比深度優(yōu)先搜括看得多雙向?qū)挾葍?yōu)先搜索深度優(yōu)先和寬度優(yōu)先搜索比較55PrimeRingProblem（ZOJ1457）Aringiscomposeofncirclesasshownindiagram.Putnaturalnumber1,2,...,nintoeachcircleseparately,andthesumofnumbersintwoadjacentcirclesshouldbeaprime.

Note:thenumberoffirstcircleshouldalwaysbe1.n(0<n<20)56while(!deque.empty()){ state=deque[0]; deque.pop(); 枚舉所有可行狀態(tài){ tempstate=狀態(tài)改變(state); deque.push_back(tempstate); }}寬度優(yōu)先搜索(BFS)寬度優(yōu)先搜索的框架57Winlinez(ZOJ1591)Nowwehaveaboardof9*9grids,onwhichthereareseveralbeads.Thesebeadshaveonlysevencolors,wenumberthem1-7.Wedefinetheemptygridtobezero.Eachturnyoucanmoveanybeadontheboardtothedestinationwherethereisaroutebetweenthem.Theroutemeansthatthebeadcanmoveup,down,leftorrighttotheadjacentemptygridandmaygoonuntilitreachesthedestination.Afterthemoving,iftherearefiveormoresame-coloredbeadsinaline(row,column,diagonal),theywillallbeeliminated.

58博弈問題給定一個有向無環(huán)圖(X,F)，其中X是一個非空的點(diǎn)集(每個點(diǎn)表示一個位置)，F(xiàn)是一個在集合X上的函數(shù)，對于集合X中的任意一個元素x，F(xiàn)(x)返回一個集合X的子集，即，F(xiàn)(x)表示了由一個位置x可以到達(dá)的位置。如果F(x)是空集，則稱x是一個結(jié)束位置?，F(xiàn)在兩個人在這樣的一個有向圖上玩游戲，首先在一個初始位置x0上放置了一個棋子，然后他們將按照如下規(guī)則進(jìn)行游戲：首先由選手I從初始位置x0進(jìn)行移動。兩個選手交替移動。在一個位置x，選手可以將棋子移到位置y上，其中y∈x。如果輪到某一個選手移動時棋子處在一個結(jié)束位置，那么這個選手就會因?yàn)闊o法繼續(xù)移動棋子而被判輸?shù)暨@局游戲。對于給定的有向圖和初始位置，請你判斷出選手I與選手II誰會獲勝。樓天城《淺談一類博弈問題的解法》59局面Ｍａｘ局面Ｍｉｎ局面終結(jié)局面局面估價函數(shù)Alpha-Beta剪枝60AMultiplicationGame

（ＺＯＪ１８９３）Stan和Ollie一起做游戲。游戲的內(nèi)容是將一個整數(shù)ｐ乘上２到９中的任一個數(shù)。Stan總是從ｐ＝１開始，然后兩個人交替相乘。在游戲開始前，兩個人訂了一個數(shù)ｎ（1<n<4294967295),誰先到達(dá)ｎ，誰就是最后的勝利者。61最大公約數(shù)最小公倍數(shù)

歐幾里得輾轉(zhuǎn)相除intgcd(inta,intb){ returnb?gcd(b,a%b):a;}intlcm(inta,intb){ returna/gcd(a,b)*b;}62篩選法求質(zhì)數(shù)表Eratosthenes（埃拉托色尼）篩選法：每次求出一個新的素?cái)?shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去。在實(shí)現(xiàn)的時候，對于一個素?cái)?shù)p，只需要篩去 等就可以了，因?yàn)橐呀?jīng)在q的第一個素因子被找到的時候被篩去了63#defineN100#defineM100intp[M],plist=0;intinit(){ memset(p,0,sizeof(p)); for(inti=2;i<=N;i++) if(!p[i]) { p[plist++]=i; intdel=i*i; while(del<=N) p[del]=1,del+=i; } returnplist;}64模算術(shù)與方程一般線性方程組aixi≡bi(modni)ax≡b(modn)x≡b1(modn1)x≡b1(modn1)x≡b1(modp1,i)用中國剩余定理其他規(guī)則同余方程二項(xiàng)方程:借助離散對數(shù)(本身??)高次方程:分解n,降冪單個多變元線性方程:消法65線性同余方程ax≡b(modn)方法一：利用Euler函數(shù)a*a(n)-1

1a(b*a(n)-1)b關(guān)鍵:求abmodna,a2,a4,a8,a16,…同余方程可以做乘法，b做二進(jìn)制展開選擇方法二：擴(kuò)展的Euclid算法存在整數(shù)y，使得ax-ny=b

記d=(a,n)，a’=a/d,n’=n/d，必須有d|ba’x-n’y=1*(b/d)注意：x不唯一,所有x相差n/d的整數(shù)倍66排列組合加法原理乘法原理組合數(shù)——C(n,m)當(dāng)n，m很大時，怎么求？排列數(shù)——P（n,m)67全排列的手工生成步驟1：從后往前找出第一個相鄰逆序?qū)?shù)。例（3，4），（1，2），設(shè)兩個數(shù)中小的那個為a步驟2：找出a以后比a大的所有的數(shù)，將這些數(shù)中最小的一個記為b步驟3：交換a，b步驟4：將原先a以后的所有數(shù)重新排序有一種排列,如何得到他的下一種全排列呢？經(jīng)過上述步驟，就得到了下個排列next_permutation?68全排列的手工生成intnext(intn,int*a){inti=n-2,j,Min;while(a[i]>a[i+1]&&i>=0)i--;if(i<0)return0;for(Min=i+1,j=i+2;j<n;j++)if(a[j]>a[i]&&a[j]<a[Min])Min=j;swap(a[i],a[Min]);for(intj=i+1;j<n;j++)for(intk=j+1;k<n;k++)if(a[j]>a[k])swap(a[j],a[k]);return1;}69Catalan數(shù)將正ｎ邊形用對角線剖分成三角形的方法數(shù)通項(xiàng)公式70Fibonacci數(shù)Fibonacci數(shù)的O(lgn)實(shí)現(xiàn)71彩票大街上到處在賣彩票，一元錢一張。購買撕開它上面的錫箔，你會看到一個漂亮的圖案。圖案有n種，如果你收集到所有n種彩票，就可以得大獎。請問，在平均情況下，需要買多少張彩票才能得到大獎呢？72分析總結(jié)已有0個圖案:拿1次就可以多搜集一個已有1個圖案:平均拿n/(n-1)次就可多搜集一個已有k個圖案:平均拿n/(n-k)次就可多搜集一個所以總次數(shù)為:n(1+1/2+1/3+…+1/n)73數(shù)值分析定積分計(jì)算(Romberg)多項(xiàng)式求根(牛頓法)線形方程組(高斯消元法)74生成樹問題最小生成樹(MST)最大生成樹??Prim算法Kruskal算法兩種算法的使用范圍75最短路問題單源最短路徑問題Dijkstra多源最短路徑問題Floyd-WarshallBellman-ford76第n短路徑第二最短路徑：枚舉最短路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些圖的最短路徑。最短的一條即為第二最短路徑第n最短路徑可以在求解第n-1最短路徑的基礎(chǔ)上求解77Arbitrage(ZOJ1092)題目大意: 有很多很多種貨幣,每兩種貨幣之間都有一個匯率,問是否能找到一種套匯(??)的方法78網(wǎng)絡(luò)流問題特點(diǎn)：2.較高的編程復(fù)雜度3.較死板的構(gòu)造方法1.較廣的使用范圍 由于后面的兩個特點(diǎn)，網(wǎng)絡(luò)流算法已經(jīng)逐步淡出了高中信息學(xué)舞臺。但在ＡＣＭ／ＩＣＰＣ競賽中，網(wǎng)絡(luò)流算法仍占據(jù)著一席之地79網(wǎng)絡(luò)流模型若有向圖G=(V,E)滿足下列條件：有且僅有一個頂點(diǎn)S，它的入度為零，即d-(S)=0，這個頂點(diǎn)S便稱為源點(diǎn)，或稱為發(fā)點(diǎn)。有且僅有一個頂點(diǎn)T，它的出度為零，即d+(T)=0，這個頂點(diǎn)T便稱為匯點(diǎn)，或稱為收點(diǎn)。每一條弧都有非負(fù)數(shù)，叫做該邊的容量。邊(vi,vj)的容量用cij表示。則稱之為網(wǎng)絡(luò)流圖，記為G=(V,E,C)80最大流最大流的定義求有向帶權(quán)圖G=(V,E,C)的一個流,它滿足容量限制條件，且原點(diǎn)提供的流量最大最大流解法Ford-FulkersonmethodPush-relabelalgorithmRelabel-to-frontalgorithm算法導(dǎo)論第26章81最小費(fèi)用最大流給定網(wǎng)絡(luò)G=（V，E，C，W），求網(wǎng)絡(luò)上的一個流f，使得f是網(wǎng)絡(luò)的最大流，且每條弧的流量與費(fèi)用的乘積加起來的總合帶上下界的最小費(fèi)用最大流最小費(fèi)用路算法消圈算法82網(wǎng)絡(luò)流算法（金愷）

難點(diǎn)：網(wǎng)絡(luò)流在具體問題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，其次是算法的優(yōu)化。構(gòu)造沒有現(xiàn)成的模式可依，只能根據(jù)題目的具體條件來分析。這需要對各種網(wǎng)絡(luò)流的性質(zhì)了如指掌，并且歸納總結(jié)一些經(jīng)驗(yàn)，發(fā)揮我們的創(chuàng)造性。一般來說，用得最多的方法是拆點(diǎn)法。優(yōu)化是算法的重要環(huán)節(jié)，它并非朝夕之功就能提高的，必須靠經(jīng)驗(yàn)的積累。83二分圖匹配問題二分圖是一類很重要的圖，它的頂點(diǎn)可以分成兩個集合X和Y，圖的所有邊一定是有一個頂點(diǎn)屬于集合X，另一個頂點(diǎn)屬于集合Y。84二分圖的最大匹配同類結(jié)點(diǎn)不鄰接。圖的一個匹配是一些邊的集合，任意兩條邊沒有公共端點(diǎn)。圖中包含邊數(shù)最多的匹配稱為圖的最大匹配匈牙利算法網(wǎng)絡(luò)流解法（Hopcroft）85二分圖的最小覆蓋定理：二分圖中點(diǎn)對邊的最小覆蓋等于其最大匹配數(shù)。M個是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個更大的匹配）M個是必須的。僅考慮形成最大匹配的這M條邊，由于它們兩兩個無公共點(diǎn)，因此至少需要M個點(diǎn)才能把它們覆蓋86二分圖的匹配二分圖的最佳匹配二分圖的完美匹配二分圖的完備匹配穩(wěn)定婚姻問題87獨(dú)立集考慮圖G=（V，E）。S是V的一個子集，如果在S中任意兩個頂點(diǎn)在G中都不是鄰接的，那么S就是G的一個獨(dú)立集。如果在G中不存在具有|S1|〉|S|，則稱S為G的最大獨(dú)立集88誘導(dǎo)子圖頂點(diǎn)-導(dǎo)出子圖另V1是圖G=(V,E)的頂點(diǎn)集V的子集,如果E1是E的子集,且邊(vi,vj)屬于E1,當(dāng)且僅當(dāng)vi和vj屬于V1,那么子圖G1=(V1,E1)就叫做G在頂點(diǎn)集V1上的導(dǎo)出子圖。如果vi和vj屬于V1，那么E中任何一條以vi和vj為端點(diǎn)的邊都屬于E189弦圖定理:如果一個圖的任何誘導(dǎo)子圖都不是K階環(huán)(K>=4),那么該圖稱為弦圖90FishingNet(ZOJ1015)判斷一個圖是否是弦圖?91計(jì)算幾何判兩條線斷相交判點(diǎn)在多邊性內(nèi)部二維凸包叉乘92OnlineJudge的簡稱一種通過網(wǎng)絡(luò)信息交互在線判題的系統(tǒng)它模擬了ICPC比賽真實(shí)的情況當(dāng)前世界上規(guī)模比較大的OJUVAZOJURALUSACOOJ是什么93Zhejianguniversityonlinejudge推薦使用：gcc+vivs2003/vs200594SubmissionError--提交使用了不正確的隊(duì)名、題號等。NoSuchProblem--檢查題號有沒有填錯？CompileError--程序不能通過編譯。RunTimeError--程序運(yùn)行過程中出現(xiàn)非正常中斷。MemoryLimitExceeded--內(nèi)存使用量超過裁判規(guī)定的上限。OutputLimitExceeded--輸出數(shù)據(jù)量過大，多半死循環(huán)了……TimeLimitExceeded--運(yùn)行超過時限還沒有得到輸出結(jié)果。WrongAnswer--答案錯誤。PresentationError--輸出格式不對，可檢查空格、回車等等細(xì)節(jié)。Accepted--恭喜恭喜！OutOfContestTime--比賽已經(jīng)結(jié)束啦！ContestRuleViolation--宣判極刑