2.9　圖論模型與算法

本節(jié)選解習題來源于《算法競賽入門經(jīng)典（第2版）》一書的第11章。

習題11-1　網(wǎng)頁跳躍（Page Hopping, ACM/ICPC World Finals 2000, UVa821）

最近的研究表明，互聯(lián)網(wǎng)上任何一個網(wǎng)頁在平均情況下最多只需要點擊19次就能到達任意一個其他網(wǎng)頁。如果把網(wǎng)頁看成一個有向圖中結(jié)點，則該圖中任意兩點間最短距離的平均值為19。

輸入一個n（1≤n≤100）個點的有向圖，假定任意兩點之間都相互到達，求任意兩點間最短距離的平均值。輸入保證沒有自環(huán)。

【分析】

模型就是帶權(quán)有向圖，權(quán)值是兩點之間的距離，則使用Floyd算法就可以計算出任意兩點之間的最短距離，最后求平均值。關(guān)于Floyd算法，請參考《算法競賽入門經(jīng)典（第2版）》中的11.2.5節(jié)。

習題11-2　奶酪里的老鼠（Say Cheese, ACM/ICPC World Finals 2001, UVa1001）

無限大的奶酪里有n（0≤n≤100）個球形的洞。你的任務(wù)是幫助小老鼠A用最短的時間到達小老鼠O所在位置。奶酪里的移動速度為10秒一個單位，但是在洞里可以瞬間移動。洞和洞可以相交。輸入n個球的位置和半徑，以及A和O的坐標，求最短時間。

【分析】

把起點A和目標點O都看作半徑為0的球，則共有n+2個球。把每個球的球心看作結(jié)點，則兩個球(p1,r1)和(p2,r2)所對應(yīng)的結(jié)點之間的距離為d=|p1-p2|-r1 – r2，如果d< 0，說明兩個球相交，可以認為d=0。求出所有頂點之間的距離之后，任意兩個球?qū)?yīng)的結(jié)點之間都有一個距離為d的無向邊。使用Floyd算法即可求出A和O之間的最短距離。

習題11-3　因特網(wǎng)帶寬（Internet Bandwidth, ACM/ICPC World Finals 2000, UVa820）

在因特網(wǎng)上，計算機是相互連通的，兩臺計算機之間可能有多條信息連通路徑。流通容量是指兩臺計算機之間單位時間內(nèi)信息的最大流量。不同路徑上的信息流通是可以同時進行的。例如，圖2.72中有4臺計算機，總共5條路徑，每條路徑都標有流通容量。從計算機1到計算機4的流通總?cè)萘渴?5，因為路徑1-2-4的容量為10，路徑1-3-4的容量為10，路徑1-2-3-4的容量為5。

請編寫一個程序，在給出所有計算機之間的路徑和路徑容量后求出兩個給定結(jié)點之間的流通總?cè)萘浚僭O(shè)路徑是雙向的，且兩方向流動的容量相同）。

【分析】

把每個計算機看作一個結(jié)點，圖2.72中每條路徑對應(yīng)有向圖中兩條邊，容量都是路徑的容量。之后應(yīng)用Dinic算法求出給定結(jié)點之間的最大流即可。關(guān)于Dinic算法，請參考《算法競賽入門經(jīng)典—訓練指南》中的5.6.1節(jié)。

習題11-4　電視網(wǎng)絡(luò)（Cable TV Network, ACM/ICPC SEERC 2004, UVa1660）

給定一個n（n≤50）個點的無向圖，求它的點連通度，即最少刪除多少個點，使得圖不連通。如圖2.73（a）所示的點連通度為3，圖2.73（b）所示的連通度為0，圖2.73（c）所示的點連通度為2（刪除1和2或者1和3）。

【分析】

注意只要使得任意兩個點不連通即可。將每個點i拆成兩個點i和i+n。建立一條有向邊i→i+n，容量為1。對于原圖中的邊(i,j)，建立兩條邊(i+n→j), (j+n→i)，容量為INF。兩兩遍歷點對(u,v)，令u+n為源點s，v為匯點t。則要使u和v不連通所需刪除的點對應(yīng)于s到t之間由容量為1的邊組成的割。這個點集大小的最小值，等于s→t最小割的容量。在所有的最小割容量中取最小值即是所求的點連通度。關(guān)于最小割的求法，請參考《算法競賽入門經(jīng)典（第2版）》中的11.4.3節(jié)。完整程序如下：

習題11-5　方程（Equation, ACM/ICPC NEERC 2007, UVa1661）

輸入一個后綴表達式f(x)，解方程f(x)=0。表達式包含四則運算符，且x最多出現(xiàn)一次。保證不會出現(xiàn)除以常數(shù)0的情況，即至少存在一個x，使得f(x)不會除0。所謂后綴表達式，是指把運算符寫在運算數(shù)的后面。例如，(4x+2)/2的后綴表達式為4 x* 2+2 /。樣例輸入與輸出如表2.3所示。

【分析】

第一步首先要將輸入的表達式解析成表達式樹，解析的過程實際上是遞歸的，輸入運算符op的位置end，得到op對應(yīng)的表達式樹，同時將end更新到解析出的表達式的左邊位置。

解析完表達式之后，求解的過程依然是遞歸的，給定一個表達式樹的根結(jié)點p，以及這個表達式的值v。因為題目條件中x只存在于一個結(jié)點，要么屬于p的左子樹，要么就是右子樹。而x所在的子樹的值就是未知的。首先根據(jù)p對應(yīng)的運算符以及v求出x所在的子樹的值（解一個一元方程），然后往下遞歸。發(fā)現(xiàn)任何無解或者有無數(shù)多個解時終止遞歸，主要是牽涉乘法和除法時有各種的特殊情況需要處理，詳情請參見代碼。

同時需要注意的是，求解的過程中的數(shù)值類型需要使用自定義的有理數(shù)類型，并且有理數(shù)的分子分母都需要使用64位的long long來保存，否則可能會溢出。

習題11-6　括號（Brackets Removal, NEERC 2005, UVa1662）

給一個長度為n的表達式，包含字母、二元四則運算符和括號，要求去掉盡量多的括號。去括號規(guī)則如下：若A和B是表達式，則A+(B)可變?yōu)锳+B，A-(B)可變?yōu)锳-B'，其中B'為B把頂層“+”與“-”互換得到；若A和B為乘法項（term），則A*(B)變?yōu)锳*B，A/(B)變?yōu)锳/B'，其中B'為B把頂層“*”與“/”互換得到。本題只能用結(jié)合律，不能用交換律和分配律。

例如，((a-b)-(c-d)-(z*z*g/f)/(p*(t))*((y-u)))去掉括號以后為a-b-c+d-z*z*g/f/p/t*(y-u)。

【分析】

首先使用《算法競賽入門經(jīng)典》中的11.1.2節(jié)中介紹的遞歸下降法對表達式進行解析，建立表達式樹。樹的結(jié)點包含：

（1）當前的運算符或字母。

（2）是否包含在括號內(nèi)。

（3）運算符的優(yōu)先級。

乘除的優(yōu)先級比加減高。解析的過程中，如果發(fā)現(xiàn)一個序列左右兩端有括號，則需要設(shè)置對應(yīng)結(jié)點的標志位。

解析完成之后，對整棵樹進行去括號的處理，處理順序是從根結(jié)點遞歸往下：

（1）對于左結(jié)點，如果其優(yōu)先級大于或等于當前結(jié)點，直接去掉其括號然后對其進行遞歸去括號處理。

（2）對于右結(jié)點，如果其優(yōu)先級高于當前結(jié)點，直接去掉其括號即可。

（3）如果右結(jié)點優(yōu)先級等于當前結(jié)點，并且發(fā)現(xiàn)需要當前結(jié)點為“-”或者“/”進行運算符的求反，如-(b-c)這樣或者/(b/c)這樣的表達式，那么就需要進行運算符取反處理，遞歸往下每次遇到左結(jié)點如果優(yōu)先級等于上級結(jié)點，就取反。

（4）右結(jié)點取反之后，再對其進行去括號處理。

習題11-7　電梯換乘（Lift Hopping, UVa 10801）

在一個假想的大樓里，有編號為0～99的100層樓，還有n（n≤5）座電梯。你的任務(wù)是從第0樓到達第k樓。每個電梯都有一個運行速度，表示到達一個相鄰樓層需要的時間（單位：秒）。由于每個電梯不一定每層都停靠，有時需要從一個電梯換到另一個電梯。換電梯時間總共1分鐘，但前提是兩座電梯都能停靠在換乘樓層。大樓里沒有其他人和你搶電梯，但你不能使用樓梯（這是一個假想的大樓，你無須關(guān)心它是否真實存在）。

例如，有3個電梯，速度分別為10、50、100，電梯1停靠0、10、30、40樓，電梯2停靠0、20、30樓，電梯3停靠第0、20、50樓，則從0樓到50樓至少需要3920秒，方法是坐電梯1到達30樓（300秒），坐電梯2到達20樓（500秒+換乘60秒），再坐電梯3到達50樓（3000秒+換乘60秒），一共300+500+60+3000+60=3920秒。

【分析】

將每一層樓內(nèi)每個電梯在該層的出口看作一個頂點，對于電梯x來說，假如它在第i層停靠，把x在i層的出口看作一個頂點記為x*100+i。對于x的下一個停靠層j來說，x* 100+j和x*100+i可以連一條邊，權(quán)值就是這個電梯從i到j層所需要的運行時間。而對于同樣在i層停靠的每個電梯y來說，x*100+i到y*100+i也連一條邊，權(quán)值為60（同層換乘）。

圖建好之后，遍歷所有的形為x*100的點u和y*100+k的v，使用dijkstra算法求出所有u、v間最短距離的最小值即為所求結(jié)果。完整程序（C++11）如下：

習題11-8　凈化器（Purifying Machine, ACM/ICPC Beijing 2005, UVa1663）

給m個長度為n的模板串。每個模板串包含字符0、1和最多一個星號“*”，其中星號可以匹配0或1。倒如，模板01*可以匹配010和011兩個串，而模板集合{*01, 100, 011}可以匹配串{001, 101, 100, 011}。

你的任務(wù)是改寫這個模板集合，使得模板的個數(shù)最少。例如，上述模板集合{*01, 100, 011}可以改寫成{0*1, 10*}，匹配到的字符串集合仍然是{001, 101, 100, 011}。n≤10，m≤1000。

【分析】

拿到一個輸入串之后，首先展開成可以匹配的串集合S，S中的元素用對應(yīng)的整數(shù)值來表示。例如{*01, 100, 011}→{101, 001, 100, 011}→{5, 1, 4, 3}。

兩兩判斷這個S中的點s1, s2，如果二者的二進制只有一位不同，在s1和s2之間連一條邊，對應(yīng)一個帶“*”的模板串，其中“*”的位置就是s1和s2不同的那一位。而s1和s2中1的個數(shù)的奇偶性必然不同。可以按照這個奇偶性將所有點分成兩類，就形成一個二分圖。而這個二分圖的每一個匹配都對應(yīng)于一個帶“*”的模板集合。求此二分圖的最大匹配，假設(shè)其中有n條邊，則所求的模板集合的最小值就是|S|-n。

完整程序如下：

習題11-9　機器人警衛(wèi)（Sentry Robots, ACM/ICPC SWERC 2012, UVa12549）

在一個Y行X列（1≤Y, X≤100）的網(wǎng)格里有空地（.）、重要位置（*）和障礙物（#），如圖2.74所示。用最少的機器人看守所有重要位置。每個機器人要放在一個格子里，面朝上、下、左、右4個方向之一。機器人會發(fā)出激光，一直射到障礙物為止，沿途都是看守范圍。機器人不會阻擋射線，但不同的機器人不能放在同一個格子。

【分析】

需要注意的是，機器人放到重要位置上，看守這個重要位置。

考慮沒有障礙物的簡單情況，實際上就是《算法競賽入門經(jīng)典—訓練指南》的第5.5.4節(jié)中的例題27（UVa11419）。建模過程如下：把每一行看作一個X結(jié)點，每一列看作一個Y結(jié)點，每個重要位置看作一條邊連接相應(yīng)的行結(jié)點和列結(jié)點。同一行或列只需要放置一個機器人，就可以看守所在同一行或同一列上的所有重要位置。這樣就要求選擇一組結(jié)點，使得每個所有重要位置對應(yīng)的邊都至少有1個結(jié)點被覆蓋。這樣就轉(zhuǎn)換成為求二分圖的最小覆蓋，可以證明最小覆蓋等于最大匹配數(shù)。

這樣，問題的關(guān)鍵就在于能否把帶有障礙物的模型轉(zhuǎn)換成為不帶障礙物的模型。首先按照行進行轉(zhuǎn)換：從上到下，從左到右遍歷每個點，遇到障礙物時，就將障礙物以及所有右邊的點（包括障礙物和重要位置）向下平移一行，這樣將左邊的點和右邊的點分割成上下兩行。如圖2.75所示為每個點的坐標以及做了上述水平轉(zhuǎn)換后的坐標。這樣，被障礙物隔開的兩邊的點就可以分成獨立的兩行，分別由單獨機器人進行看守。同理，按行進行轉(zhuǎn)換之后，繼續(xù)按照列進行類似的轉(zhuǎn)換。

轉(zhuǎn)換完成之后，點水平和垂直坐標的最大值分別是X+2*W、Y+2*W，這也是建成的二分圖的X和Y點數(shù)的最大值，而重要位置的個數(shù)（也就是說二分圖的邊數(shù)）依然是P。完整程序（C++11）如下：

習題11-11　占領(lǐng)新區(qū)域（Conquer a New Region, ACM/ICPC Changchun 2012, UVa1664）

假設(shè)n（n≤200000）個城市形成一棵樹，每條邊有權(quán)值C(i,j)。任意兩個點的容量S(i,j)定義為i與j唯一通路上容量的最小值。找一個點（它將成為中心城市），使得它到其他所有點的容量之和最大。

【分析】

因為是一棵樹，任意一條邊都可以將整個圖分成兩棵樹，所求的中心點一定是在其中一棵樹中，由此想到一開始可以從每個點開始求中心點，然后不斷合并。

參考Kruskal算法的思路，首先初始化并查集，一開始每個集合的代表元素都是中心點，維護每個點集的元素個數(shù)Cnt[i]以及中心點到其他點的容量之和WS[i]，其中i是這個元素的代表元，一開始i肯定是所在點集的中心城市，且WS[i]=0。

把所有邊按權(quán)值從大到小排序，依次遍歷每條邊e，使用e將已有兩個點集連起來。記這兩個點集為A、B，中心點分別是a、b。因為已經(jīng)排序，e一定是連接來自兩個點集的邊中權(quán)值最小的，而且分別來自A和B的任意兩點之間的唯一通路一定經(jīng)過e，所以通路的容量一定為e的權(quán)值。

然后考慮A和B合并之后的點集，如果要把b作為其中心點，產(chǎn)生的新的點集的容量就是W_b=WS[b]+Cnt[a]*w，其中w是e的權(quán)值。而b到A中每個點的容量都是w。反過來把a作為中心點產(chǎn)生的新點集容量是W_a=WS[a]+Cnt[b]*w。不妨設(shè)W_a>W_b，把B合并到A中，a就是新的點集的符合要求的中心點。所有邊遍歷完成之后，合并完成的集合的代表元就是所求的中心點，算法的時間復雜度為O(N)。完整程序如下：

本題的嚴格證明留給讀者思考。

習題11-12　島嶼（Islands, ACM/ICPC CERC 2009, UVa1665）

輸入一個n*m（1≤n,m≤1000）矩陣，每個格子里都有一個[1,10⁹]正整數(shù)。再輸入T（1≤T≤10⁵）個整數(shù)t_i（0≤t₁≤t₂≤…≤t_T≤10⁹)，對于每個t_i，輸出大于t_i的正整數(shù)組成多少個四連塊。如圖2.76所示，大于1的正整數(shù)組成兩塊，大于2的組成3塊。

評論：這個題目雖然和圖論沒什么關(guān)系，但是可以用到本章介紹的某個數(shù)據(jù)結(jié)構(gòu)。

【分析】

因為牽涉集合的查詢合并，首先可以使用并查集來表示連續(xù)的格子組成的集合。最簡單的做法就是從大到小遍歷所有的t，每次查找對應(yīng)的格子，但是粗略估計時間復雜度至少是T*n*m=10¹¹，必然會超時。這樣可以將所有的格子按照值從大到小排序，然后每次只查找對應(yīng)的格子，并且復用上次遍歷的結(jié)果。

具體來說，可以用一個結(jié)構(gòu)P{x,y,v}表示位置是[x,y]且值為v的數(shù)字。然后按照v從大到小對所有的P排序，初始每個P屬于一個獨立的集合（塊）。之后按照從大到小的順序，遍歷t_i。記ans為開始遍歷時符合條件的集合的個數(shù)。i=T則ans=0，否則ans初始就是t_i+1對應(yīng)的結(jié)果。從大到小依次掃描t_i+1>v>t_i的所有點p。每遍歷到一個p，ans加1，然后依次查看p在矩陣中的4個鄰居pn，如果pn.v > t_i，且pn和p不在同一個集合，則將pn和p所在的集合合并，ans減1。掃描完符合條件的P之后ans就是符合v> t_i的集合個數(shù)。

雖然是兩層循環(huán)，但是內(nèi)層循序?qū)嶋H上是不重復地遍歷所有格子，總的循環(huán)次數(shù)是nm。時間復雜度為O(nm*α(mn)+T)。這里α表示并查集查找過程的時間復雜度，基本上可以認為是常量，不大于4，具體的分析請參考《算法導論》一書的21.4節(jié)。完整程序（C++11）如下：

習題11-14　亂糟糟的網(wǎng)絡(luò)（Network Mess, ACM/ICPC Tokyo 2005, UVa1667）

有一棵n（n≤50）個葉子的無權(quán)樹。輸入兩兩葉子的距離，恢復出這棵樹并輸出每個非葉子結(jié)點的度數(shù)。

【分析】

面對這種無根的樹型結(jié)構(gòu)，一般一開始就任意取一個葉子結(jié)點u作為根。記f(i,j)為i和j兩個葉子之間的距離。

遞歸處理：輸入以u為根的子樹的所有葉子結(jié)點以及u到所有葉子的距離。枚舉它的任意兩個葉子i、j，如圖2.77所示。

（1）f(u,i)+f(u,j) > f(i,j)，說明i和j是在u為根的樹的同一個子樹。

（2）f(u,i)+f(u,j)=f(i,j)，說明i和j不在同一棵子樹中。

然后用并查集對所有的u的葉子進行分組，分成不同的子樹，同時創(chuàng)建對應(yīng)的子樹根。在往下遞歸之前，應(yīng)該將所有的葉子結(jié)點到根結(jié)點的距離都減一。

在這個過程中，對于f(u,i)=1的情況，說明i就是u的直接葉子結(jié)點，不需要往下遞歸，但是需要構(gòu)造一個相應(yīng)的葉子結(jié)點方便進行統(tǒng)計。通過上述邏輯，就可以找出哪些葉子在同一棵子樹中，以及u有多少棵子樹。完整程序（C++11）如下：

習題11-16　交換房子（Holiday's Accomodation, ACM/ICPC Chengdu 2011, UVa1669）

有一棵n（2≤n≤10⁵）個結(jié)點的樹，每個結(jié)點住著一個人。這些人想交換房子（即每個人都要去另外一個人的房子，并且不同人不能去同一個房子）。要求安排每個人的行程，使得所有人旅行的路程長度之和最大。

【分析】

因為是一棵樹，安排好的符合條件的行程中，假如有兩對結(jié)點（u1,u2）和（v1,v2）。u1要到v1，u2要到v2，而且這兩條路徑不相交。那么在兩條路徑上分別選擇點p1和p2，則重新做如下安排：u1→p1→p2→v2，u2→p2→p2→v2，其中記p1→p2的路徑長度為pl，顯然這樣安排的路徑相交而且長度之和比之前的長度長2*pl。由此可以證明，任意兩個行程的路徑必定相交。

首先任選一個結(jié)點作為根，構(gòu)造整棵樹，同時對每個結(jié)點u記錄以u為根結(jié)點的子樹的結(jié)點個數(shù)D_u。然后對于每個長度為w的邊e，假設(shè)這條邊將樹分成A、B兩顆子樹，根據(jù)上述結(jié)論可以得出經(jīng)過這條邊的路徑的條數(shù)就是m_e=2*min{D_A, n-D_A}。對所有邊求即可得所求結(jié)果。至于如何求每顆子樹的結(jié)點個數(shù)，可以使用《算法競賽入門經(jīng)典（第2版）》中的9.4.2節(jié)，《樹的重心》部分的樹形DP過程。

習題11-17　王國的道路圖（Kingdom Roadmap, ACM/ICPC NEERC 2011, UVa1670）

輸入一個n（n≤100000）個結(jié)點的樹，添加盡量少的邊，使得任意刪除一條邊之后圖仍然連通。如圖2.78所示，最優(yōu)方案用虛線表示。

【分析】

要滿足所求的條件，保證結(jié)果的圖中沒有橋即可，可將每個葉子都和其他葉子相連。任意選擇一個度數(shù)為1的非葉子結(jié)點作為樹根，然后依次對每顆子樹進行遞歸操作。

對于每顆子樹：把懸在橋上的葉子依次配對連起來，但是要保證留下至少一個傳回給父結(jié)點，以便最終和根結(jié)點配對。對于根結(jié)點，如果剩下兩個葉子，就把它們連起來，如果剩一個，就在這個葉子和根結(jié)點之間連一條邊。

證明留給讀者思考。完整程序（C++11）如下：

習題11-20　租車（Rent a Car, UVa12433）

如果你想經(jīng)營一家租車公司。接下來的N天中已經(jīng)有了一些訂單，其中第i天需要rj輛車（0≤r_j≤100）。初始時，你的倉庫是空的，需要從C家汽車公司買車，其中第i家公司里有c_i輛車，單價是p_i（1≤c_i,p_i≤100）。當一輛車被歸還給租車公司之后，你必須把它送去保養(yǎng)之后才能再次租出去。一共有R家服務(wù)中心，其中第i家保養(yǎng)一次需要d_i天，每輛車的費用為s_i（1≤d_i,s_i≤100）。這些服務(wù)中心都很大，可以接受任意多輛車同時保養(yǎng)。你的倉庫很大，可以容納任意多輛車。你的任務(wù)是用最小的費用滿足所有訂單。1≤N,C, R≤50。

例如，N=3，C=2，R=1，r={10,20,30}，c₁=40，p₁=90，c₂=15，p₂=100。d₁=1，s₁=5，最優(yōu)方案是這樣的：先買50輛車，其中在公司1買40輛，公司2買10輛，費用為90*40+100*10=4600。第一天白天租出去10輛車，晚上收回之后送到服務(wù)中心保養(yǎng)一天，費用為5*10=50，第3天白天可以再次出租。第2天出租20輛車，第3天把剩下的20輛車和保養(yǎng)后的10輛車一起出租。總費用為4600+50=4650。

【分析】

建立源點S和匯點T。對于第i天，建立兩個結(jié)點G_i和Q_i，分別表示當天的待租車庫，以及待保養(yǎng)車庫（存放當天返回的待保養(yǎng)車），從G_i到T建立一條邊，容量為當天的市場需求r_i，費用為0，表示當天需要租出r_i輛車。從S到Q_i建一條邊，容量為r_i，費用為0，代表從市場歸還的r_i輛車。從G_i-1到G_i建立一條邊，容量為INF，費用為0。表示汽車可以在租車公司存著不租出去。而對于每一個汽車公司，從S到G₀建立一條容量為c，費用為p的邊，表示第一天可以買到的車。

對于每個服務(wù)中心，因為從第i天市場返回來的車要在第i+1天送修并且在第i+d+1天才送回租車公司供后續(xù)出租，所以從Q_i到G_i+d+1，建立一條邊（前提是i+d+1 < N），容量為INF，費用為保養(yǎng)費用s。圖2.79展示了題目描述案例對應(yīng)的圖的結(jié)構(gòu)。

這樣S→T的最小費用就是所求的最小費用，直接用MCMF求最小費用最大流即可，求出最小費用之后，看每條到T的邊容量是否是最大值，也就是說滿足了當天的市場需求。如果全部滿足，直接輸出最小費用，否則說明不滿足，輸出impossible。

這個題目的難點在于：如何表示從服務(wù)中心保養(yǎng)返回的車，實際上這些流量是在每一天“返回”了，那么就從源點到每一天的待保養(yǎng)車庫建一條邊即可，表示流量用完之后又“回來”了。另外對于服務(wù)中心及汽車公司，雖然直觀概念上是一個點，但是本質(zhì)上只是有費用流量的路徑而已，不用在建模時建立這個點，直接建邊即可。

MCMF算法的實現(xiàn)可以參考《算法競賽入門經(jīng)典—訓練指南》中的5.6.2節(jié)。費用要使用64位的long long來存儲，以免溢出。