第一篇：個人網(wǎng)絡(luò)流知識小結(jié)

個人網(wǎng)絡(luò)流知識小結(jié)好啊，入門資料，包括簡單介紹網(wǎng)絡(luò)流的知識概念以及Dinic的算法介紹，主要思想就是bfs進(jìn)行分層，在dfs找增廣路徑，以及ISAP算法介紹，很全了

HDU3549 最簡單的網(wǎng)絡(luò)流入門題，poj1273 先是寫了最基礎(chǔ)的 Edmonds-karp(EK)算法，時間復(fù)雜度為O(VE2)有鄰接矩陣的實(shí)現(xiàn)，還有鄰接邊的實(shí)現(xiàn)，后者容易出錯！編程復(fù)雜度加大，不過效率較矩陣高

對于EK算法與ISAP算法的區(qū)別：

EK算法每次都要重新尋找增廣路，尋找過程只受殘余網(wǎng)絡(luò)的影響，如果改變殘余網(wǎng)絡(luò)，則增廣路的尋找也會隨之改變；SAP算法預(yù)處理出了增廣路的尋找大致路徑，若中途改變殘余網(wǎng)絡(luò)，則此算法將重新進(jìn)行。EK處理在運(yùn)算過程中需要不斷加邊的最大流比SAP更有優(yōu)勢

3.Dinic算法 O(v2E)代碼分別有遞歸的實(shí)現(xiàn)，和非遞歸的實(shí)現(xiàn)版本

算法思想主要如下：

1.初始化流量，計算出剩余圖

2.根據(jù)剩余圖，計算層次圖，如果匯點(diǎn)不在層次圖中，那么算法結(jié)束

3.在層次圖內(nèi)不斷用bfs增廣，直到層次圖內(nèi)沒有增廣路為止

轉(zhuǎn)2

4.ISAP算法，別人寫的很好，理解了，直接摘抄了，引用http:///?p=34 眾所周知，在網(wǎng)絡(luò)流的世界里，存在2類截然不同的求解思想，就是比較著名的預(yù)流推進(jìn)與增廣路，兩者都需要反向邊的小技巧。

其中預(yù)流推進(jìn)的算法思想是以邊為單元進(jìn)行推流操作。具體流程如下:置初始點(diǎn)鄰接邊滿流并用一次反

向bfs對每個結(jié)點(diǎn)計算反向距離標(biāo)號，定義除匯點(diǎn)外存量大于出量的結(jié)點(diǎn)為活動結(jié)點(diǎn)，每次對活動結(jié)點(diǎn)按允許邊（u->v:d[u]=d[v]+1）進(jìn)行推流操作，直到無法推流或者該點(diǎn)存量為0，若u點(diǎn)此時仍為活動結(jié)點(diǎn)，則進(jìn)行重標(biāo)號，使之等于原圖中進(jìn)行推操作后的鄰接結(jié)點(diǎn)的最小標(biāo)號+1，并將u點(diǎn)入隊。當(dāng)隊列為空時，算法結(jié)束，只有s點(diǎn)和t點(diǎn)存量非0，網(wǎng)絡(luò)中各頂點(diǎn)無存量，無法找到增廣路繼續(xù)增廣，則t點(diǎn)存量為最大流。

而增廣路的思想在于每次從源點(diǎn)搜索出一條前往匯點(diǎn)的增廣路，并改變路上的邊權(quán)，直到無法再進(jìn)行增廣，此時匯點(diǎn)的增廣量即為最大流。兩者最后的理論基礎(chǔ)依然是增廣路定理，而在理論復(fù)雜度上預(yù)流推進(jìn)要顯得比較優(yōu)秀。其中的HLPP高標(biāo)預(yù)流推進(jìn)的理論復(fù)雜度已經(jīng)達(dá)到了另人發(fā)指的O（sqrt(m)*n*n），但是其編程復(fù)雜度也是同樣的令人發(fā)指--

于是我們能否在編程復(fù)雜度和算法復(fù)雜度上找到一個平衡呢，答案是肯定的。我們使用增廣路的思想，而且必須進(jìn)行優(yōu)化。因?yàn)樵嫉脑鰪V路算法（例如EK）是非常悲劇的。于是有人注意到了預(yù)流推進(jìn)中的標(biāo)號法，在增廣路算法中引入允許弧概念，每次反搜殘留網(wǎng)絡(luò)得到結(jié)點(diǎn)標(biāo)號，在正向增廣中利用遞歸進(jìn)行連續(xù)增廣，于是產(chǎn)生了基于分層圖的Dinic算法。一些人更不滿足于常規(guī)Dinic所帶來的提升，進(jìn)而加入了多路分流增廣的概念，即對同一頂點(diǎn)的流量，分多路同時推進(jìn)，再加上比較復(fù)雜的手工遞歸，使得Dinic已經(jīng)滿足大部分題目的需要。

然而這樣做就是增廣路算法優(yōu)化的極限么？答案永遠(yuǎn)是不。人們在Dinic中只類比了預(yù)流推進(jìn)的標(biāo)號技術(shù)，而重標(biāo)號操作卻沒有發(fā)揮得淋漓盡致。于是人們在Dinic的基礎(chǔ)上重新引入了重標(biāo)號的概念，使得算法無須在每次增廣后再進(jìn)行BFS每個頂點(diǎn)進(jìn)行距離標(biāo)號，這種主動標(biāo)號技術(shù)使得修正后算法的速度有了不少提高。但這點(diǎn)提高是不足稱道的，人們又發(fā)現(xiàn)當(dāng)某個標(biāo)號的值沒有對應(yīng)的頂點(diǎn)后，即增廣路被截斷了，于是算法便可以提前結(jié)束，這種啟發(fā)式的優(yōu)化稱為Gap優(yōu)化。最后人們結(jié)合了連續(xù)增廣，分層圖，多路增廣，Gap優(yōu)化，主動標(biāo)號等窮兇極惡的優(yōu)化，更甚者在此之上狂搞個手動遞歸，于是產(chǎn)生了增廣路算法的高效算法–ISAP算法。

雖然ISAP算法的理論復(fù)雜度仍然不可超越高標(biāo)預(yù)流推進(jìn)，但其編程復(fù)雜度已經(jīng)簡化到發(fā)指，如此優(yōu)化，加上不遜于Dinic的速率（在效率上手工Dinic有時甚至不如遞歸ISAP），我們沒有不選擇它的理由。

5.自己的理解

不管怎樣，普通的EK一般來說 復(fù)雜度是在O(n*m*m)的，而Dinic和ISAP都是O(n*n*m)d的，而ISAP的幾個優(yōu)化，有將效率進(jìn)一步提升，關(guān)于復(fù)雜度的分析，算法導(dǎo)論有介紹，主要是理解下后面的分層思想和預(yù)留推進(jìn)思想，以及根據(jù)dfs回朔來判斷是否可以推進(jìn)流還是做重標(biāo)記等，這里可以用ISAP算法和DInic算法，其中主要難點(diǎn)是在網(wǎng)絡(luò)流的建模上！鄰接表的建立也有許多巧妙之處，僅僅是數(shù)據(jù)結(jié)構(gòu)上的鄰接表，效率和空間浪費(fèi)的簡直令人發(fā)指！

接下來就是深入的部分，可以看得資料和論文如下：

很好，很全面的學(xué)習(xí)資料和總結(jié)題集《Network Flows-Theory, Algorithms, And Applications》

《Combinatorial optimization:networks and matroids》

解決網(wǎng)絡(luò)流的幾種方案在這里，非常清楚

http://dantvt.is-programmer.com/tag/Dinic

/Files/panzhizhou/國家集訓(xùn)隊論文網(wǎng)絡(luò)流整理.zip

第二篇：網(wǎng)絡(luò)編碼知識小結(jié)

注：本小結(jié)報告來自兩份論文

[1]上角標(biāo)1代表 論文 <網(wǎng)絡(luò)編碼的研究進(jìn)展> 楊林 鄭剛等

[2]上角標(biāo)2代表 論文 <網(wǎng)絡(luò)編碼研究綜述> 陶少國等

網(wǎng)絡(luò)編碼研究綜述

萬里 基本概念

起源：R.Alshwede的蝴蝶網(wǎng)絡(luò)模型定義：網(wǎng)絡(luò)編碼是一種融合編碼和路由的信息交換技術(shù)，在傳統(tǒng)存儲轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過允許對接收的多個數(shù)據(jù)包進(jìn)行編碼信息融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)整體性[1]能。

[1]本質(zhì)：利用節(jié)點(diǎn)的計算能力提高鏈路帶寬的利用率。核心思想：具備編碼條件的網(wǎng)絡(luò)節(jié)點(diǎn)對接收到的信息進(jìn)行編碼，然后傳輸給下一級的網(wǎng)絡(luò)節(jié)點(diǎn)，收到信息的下一級節(jié)點(diǎn)如果具備編碼條件，又對其接受的信息按照同樣的方式進(jìn)行傳輸與處理，如此反復(fù)，直到所有經(jīng)過處理后的信息匯聚到信宿節(jié)點(diǎn)為止。最后，在信宿節(jié)點(diǎn)，[2]通過譯碼，即可譯出信源發(fā)送的原始信息。主要優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)： 提升網(wǎng)絡(luò)吞吐量 2 均衡網(wǎng)絡(luò)負(fù)載

從作者的例子[Fig.2]可以看出，雖然傳輸鏈路增加了，但是每條鏈路上傳輸?shù)男畔⒏猓鉀Q了網(wǎng)絡(luò)擁塞問題。3 提高帶寬利用率

同2，雖然傳輸鏈路增多了，但是每條鏈路上的信息減少了（均衡了），總體是減少了網(wǎng)絡(luò)帶寬，提高了網(wǎng)絡(luò)帶寬利用率。缺點(diǎn)：

雖然網(wǎng)絡(luò)編碼優(yōu)點(diǎn)突出, 但運(yùn)用網(wǎng)絡(luò)編碼增加了計算的復(fù)雜性, 而且網(wǎng)路節(jié)點(diǎn)需要緩存足夠的輸入信息, 因此編碼操作增加了傳輸時延和節(jié)點(diǎn)的額外的I/ O、CPU消耗。統(tǒng)計數(shù)據(jù)表明, 即使應(yīng)用最有效的隨機(jī)網(wǎng)絡(luò)編碼，其編碼和譯碼的時間也不容忽視。此外, 應(yīng)用網(wǎng)絡(luò)編碼還存在同步問題, 這主要是由于信宿節(jié)點(diǎn)必須等待收到足夠的編碼信息, 才能開始

[2]譯碼。同步問題給在實(shí)時系統(tǒng)中應(yīng)用網(wǎng)絡(luò)編碼提出了挑戰(zhàn)。

[2] 2 原理與數(shù)學(xué)模型

2.1網(wǎng)絡(luò)編碼分類

網(wǎng)絡(luò)編碼按照節(jié)點(diǎn)輸出和輸入的關(guān)系可劃分為線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)編碼按照編碼系數(shù)生成的隨機(jī)性可劃分為隨機(jī)網(wǎng)絡(luò)編碼和確定性網(wǎng)絡(luò)編碼（通過算[1] 法算出系數(shù)）2.2線性網(wǎng)絡(luò)編碼

目前的網(wǎng)絡(luò)編碼研究均局限于有限域中的線性網(wǎng)絡(luò)編碼。2.3幾個基本概念 信息流：信源發(fā)送的信息，鏈路傳輸?shù)男畔⒁约靶潘藿邮盏降男畔ⅲ韵蛄啃问饺?/p>

[2]之于有限域。稱其為信息流。本地編碼向量:將節(jié)點(diǎn)上的信息流作為節(jié)點(diǎn)輸入鏈路上傳輸信息的線性組合。[鏈路的消息流與輸入鏈路的消息流的映射關(guān)系] 3 全局編碼向量:將信源發(fā)送信息表示成信息流向量，將鏈路上傳輸?shù)男畔⒘鳟?dāng)做信源向量的信息流向量各元素的線性組合，該線性組合系數(shù)構(gòu)成的向量就是該鏈路的全局編碼向量。[鏈路的消息流與信源的信息流的映射關(guān)系] 備注：如果忘記 可以參考論文2中的Fig.3 2.4數(shù)學(xué)模型

[2] 3網(wǎng)絡(luò)編碼的構(gòu)造方法

網(wǎng)絡(luò)編碼的KEY：求得每條鏈路對應(yīng)的編碼向量 3.1集中式編碼方法 3.1.1 指數(shù)時間算法

設(shè)N1,N2,...,Nn表示所有編碼鏈路對應(yīng)的編碼向量, 則必定存在函數(shù)關(guān)系: p = f(N1,N2,..,Nn),并稱使p=0的點(diǎn)(N1,N2 , ?,Nn)的集合稱為被“函數(shù)p 分割出來的代數(shù)簇”,[2]因而算法的目標(biāo)就是求得一個不位于“函數(shù)p分割出來的代數(shù)簇”上的點(diǎn)(p?0)。3.1.2 多項(xiàng)式時間算法

3.1.3其他算法 1引入通用LCM（貪婪算法與啟發(fā)式算法）可實(shí)現(xiàn)多速率的網(wǎng)絡(luò)編碼

但是由于計算量大，實(shí)現(xiàn)過程復(fù)雜，不實(shí)用（作為多速率網(wǎng)絡(luò)編碼的探索，具有很重要的意義）

2線性多播、線性廣播和線性擴(kuò)散：線性擴(kuò)散是線性廣播的特例, 線性廣播是線性多播的特例, 反之不成立.線性廣播說明了通過增加信源發(fā)送的信息流向量的維數(shù), 可以提升傳輸

[2]速率;線性擴(kuò)散能保證信源節(jié)點(diǎn)以互補(bǔ)的形式發(fā)送信息流。

[1]3沖突圖法、矩陣滿秩法、圖染色法等幾種構(gòu)造方法。3.2分布式編碼方法 3.2.1確定系數(shù)構(gòu)造法

其核心思想是將網(wǎng)絡(luò)拓?fù)浞纸獬啥鄠€子樹，并保證每個子樹的編碼矢量屬于其父樹編碼

[1]矢量的擴(kuò)張空間，且任意兩個子樹的共有信宿的編碼矢量均線性無關(guān)。3.2.2隨機(jī)系數(shù)網(wǎng)絡(luò)編碼

隨機(jī)網(wǎng)絡(luò)編碼(簡稱RNC),該方法基于一種隨機(jī)選擇編碼向量的策略:對于除了信宿節(jié)點(diǎn)外的所有中間節(jié)點(diǎn),只要在一個足夠大的有限域上隨機(jī)選擇它們輸入鏈路到輸出鏈路的映射,而且各節(jié)點(diǎn)映射關(guān)系的選取是相互獨(dú)立的,就能以較高概率使各個信宿節(jié)點(diǎn)對應(yīng)的系統(tǒng)轉(zhuǎn)移矩陣滿秩,即各信宿節(jié)點(diǎn)能以較高的概率成功譯碼。與時間多項(xiàng)式算法總能保證成功譯碼不同, 在RNC 中,雖然不能確保最終形成的系統(tǒng)轉(zhuǎn)移矩陣M滿秩, 但由于是隨機(jī)選擇編碼向量, 其復(fù)雜性與確定性算法相比要低得多, 更易于實(shí)現(xiàn), 而且99%以上的譯碼成功率在一般情況也足以滿足需求.因此,隨機(jī)網(wǎng)絡(luò)編碼具有重要的理論價值和應(yīng)用價值，得到了廣泛的關(guān)注和

[2]應(yīng)用, 如微軟提出的P2P文件共享系統(tǒng)Avalanche便是基于RNC的典型應(yīng)用。3.3集中式與分布式的比較

集中式：需要了解全局拓?fù)湟苑峙渚幋a系數(shù)，可擴(kuò)展性差。

確定分布式：掌握局部拓?fù)浼纯蓪θ刖幮畔⑦M(jìn)行編碼，但需要通信開銷。

[1]隨機(jī)網(wǎng)絡(luò)編碼：實(shí)用性強(qiáng)，需要較大的字母表，存在解碼失敗概率。

4性能參考以及優(yōu)化

網(wǎng)絡(luò)編碼的主要性能指標(biāo)包括字母表、編解碼速度和編碼增益等．其中，字母表是最重要的性能指標(biāo)，決定了網(wǎng)絡(luò)編碼解的存在性、編解碼復(fù)雜度、延時以及存儲開銷．編解碼速度反映了編解碼操作的計算復(fù)雜度．編碼增益則表征網(wǎng)絡(luò)帶寬的利用效率．網(wǎng)絡(luò)編碼設(shè)計的一個重要目標(biāo)就是盡可能使用小的字母表和低復(fù)雜度的編解碼操作來提高網(wǎng)絡(luò)吞吐量或減[1]小延時．

4.1網(wǎng)絡(luò)編碼復(fù)雜性的影響因素分析 4.1.1編碼構(gòu)造方法

網(wǎng)絡(luò)編碼的核心，目標(biāo)是尋找復(fù)雜性低的算法（分布式與集中式的共同目標(biāo)）。4.1.2編碼操作數(shù)

可從三個角度分析：信息分組、編碼鏈路和編碼節(jié)點(diǎn), 其中從信息分組的角度減少其操作數(shù)目是降低編碼操作復(fù)雜性最理想的方式, 但是分析的難度較大, 一般均從減少編碼鏈

[2]路或者節(jié)點(diǎn)的數(shù)目來考慮。4.1.3有限域的大小

保證足夠的譯碼成功率的前提下（有限域過小，譯碼成功率降低）, 應(yīng)盡量減少有限域的大小。

4.2基于簡單網(wǎng)絡(luò)的解決方案

將普通網(wǎng)絡(luò)轉(zhuǎn)化為某種易于表達(dá), 且各網(wǎng)絡(luò)節(jié)點(diǎn)具有共同特征的“簡單網(wǎng)絡(luò)”將普通網(wǎng)絡(luò)轉(zhuǎn)化為簡單網(wǎng)絡(luò), 其網(wǎng)絡(luò)拓?fù)渥兊檬趾唵?但一個不容忽視的問題就是: 簡單網(wǎng)絡(luò)的規(guī)模(節(jié)點(diǎn)數(shù))比原普通網(wǎng)絡(luò)卻膨脹了許多, 也就是說網(wǎng)絡(luò)編碼的代價被放大了,“簡單網(wǎng)絡(luò)”的最小代價并不等于原網(wǎng)絡(luò)的最小代價.但是, 將網(wǎng)絡(luò)“簡化”處理的思想在方法論上具有

[2]重要的借鑒意義,為最小代價的網(wǎng)絡(luò)編碼提供了研究方向。4.3基于信息流

信息流分解的基本原理是按照網(wǎng)絡(luò)中信息流的特征和共性, 將原網(wǎng)絡(luò)節(jié)點(diǎn)劃分為一系列的子樹圖, 這些子樹圖中的節(jié)點(diǎn)擁有相同的編碼向量, 子樹里面的節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)不影

[2]響整個系統(tǒng)的多播傳輸, 因此每個子樹可以當(dāng)作一個節(jié)點(diǎn)來處理。4.4基于最小代價函數(shù)的解決方案

借鑒路由多播的最小代價樹，將網(wǎng)絡(luò)編碼轉(zhuǎn)化為線性規(guī)劃問題。

5應(yīng)用與研究趨勢

5.1應(yīng)用領(lǐng)域

[1]Ad Hoe網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)、P2P內(nèi)容分發(fā)、分布式文件存儲和網(wǎng)絡(luò)安全等領(lǐng)域。

[2]無線網(wǎng)絡(luò)、應(yīng)用層多播和P2P文件共享、傳輸?shù)牟铄e控制。5.2研究趨勢

5.2.1多源網(wǎng)絡(luò)編碼

對于信源數(shù)目大于2的網(wǎng)絡(luò)編碼多播，研究不夠充分，但多源多播廣泛存在。5.2.2非組播網(wǎng)絡(luò)

對于非組播網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼理論研究。5.2.3非線性網(wǎng)絡(luò)編碼

非線性研究尚未起步，性能還不可知，比線性網(wǎng)絡(luò)編碼要求與難度更高。5.2.4具體實(shí)現(xiàn)

網(wǎng)絡(luò)編碼的具體實(shí)現(xiàn)需要考慮諸多因素，也是有意義的研究方向。5.2.5與其他領(lǐng)域的融合

與信源編碼的聯(lián)合設(shè)計與優(yōu)化、與信道編碼和調(diào)制技術(shù)的結(jié)合、與多描述分層編碼的結(jié)合。

5.2.6降低網(wǎng)絡(luò)編碼復(fù)雜度

降低網(wǎng)絡(luò)編碼復(fù)雜度，實(shí)現(xiàn)最小代價網(wǎng)絡(luò)編碼。5.2.7安全方面

無線網(wǎng)絡(luò)編碼在安全方面的研究。

第三篇：甲流小結(jié)

幼兒園甲型流感防控工作督導(dǎo)檢查小結(jié)

為了認(rèn)真落實(shí)甲型流感防治工作，保障廣大人民群眾的身體健康，根據(jù)《甲型流感診療指南》，結(jié)合上級衛(wèi)生行政部門指示，按照“托幼機(jī)構(gòu)（小學(xué)）甲型流感防治措施要點(diǎn)”和責(zé)任狀的規(guī)定，我站成立了托幼機(jī)構(gòu)甲型流感防控工作督導(dǎo)檢查小組，對本區(qū)范圍內(nèi)的一所托幼機(jī)構(gòu)和小學(xué)進(jìn)行了分包負(fù)責(zé)，每處由兩名防疫人員負(fù)責(zé)進(jìn)行督導(dǎo)檢查，本周進(jìn)行了 2 次督導(dǎo)檢查，發(fā)現(xiàn)問題并提出了整改意見，做好了督導(dǎo)記錄，并保存?zhèn)洳椤，F(xiàn)對本周督導(dǎo)檢查情況做小結(jié)如下：

一、托幼機(jī)構(gòu)

在對幼兒園檢查工作中，發(fā)現(xiàn)該幼兒園主要存在以下問題：

1、幼兒園兒童一部分兒童由學(xué)校班車接送，班車坐墊未每天更換。

2、大型玩具未消毒。

3、流動洗手無充足水源。

4、教室未進(jìn)行定期消毒。

針對以上問題提出了整改意見，班車坐墊要每天更換，改善寢室條件，做好各項(xiàng)消毒工作，及時做好記錄。

二、小學(xué)

在對小學(xué)檢查工作中，發(fā)現(xiàn)該學(xué)校主要存在以下問題：

1、學(xué)校班車坐墊未每天更換，消毒記錄不完整。

2、班級晨檢流于形式。

針對以上問題提出了整改意見，要求其認(rèn)真做好班車消毒并留有記錄，坐墊要每天更換。加強(qiáng)晨午檢和班級消毒工作，做好記錄。

在本周的督導(dǎo)檢查中，未發(fā)現(xiàn)我區(qū)有患甲型流感兒童。

第四篇：網(wǎng)絡(luò)安全問題---個人小結(jié)

網(wǎng)絡(luò)安全問題-----個人小結(jié)

隨著互聯(lián)網(wǎng)事業(yè)的飛速發(fā)展,精彩的網(wǎng)絡(luò)世界不可阻擋地走進(jìn)了我們的生活。計算機(jī)互聯(lián)網(wǎng)作為開放式信息傳播和交流工具，已經(jīng)走進(jìn)了我們的生活?；ヂ?lián)網(wǎng)的發(fā)展一方面為我們的學(xué)習(xí)、交流以及娛樂提供了更為寬廣的天地，但是另一方面，由于互聯(lián)網(wǎng)資源魚龍混雜、良莠不齊，致使缺乏自律能力的同學(xué)通宵達(dá)旦沉湎其中，對學(xué)業(yè)、健康和思想都造成了巨大的危害。所以,對于未成年人來說，互聯(lián)網(wǎng)是一把鋒利的“雙刃劍”。

積極作用：

1、快速掌握多方面知識的重要途徑

網(wǎng)絡(luò)已經(jīng)成為一種獲取知識的重要來源。全世界各大圖書館的資料大多可以通過網(wǎng)絡(luò)獲得，它不僅快捷而且也省去了大量的額外的花銷。網(wǎng)上還有新聞，資料，經(jīng)濟(jì)，娛樂，文學(xué)等各種信息。在網(wǎng)上，中學(xué)生可以看到最新，最快，最權(quán)威的新聞，可以學(xué)到書本上沒有的知識，了解到更廣泛的未知信息，也使更多的學(xué)生更快、更早、更接近科技前沿，使我們更加的熱愛科學(xué)，祟尚科學(xué)。

2、接受教育的有效方式

據(jù)了解，有許多學(xué)生喜歡“網(wǎng)?！边@種新式的教學(xué)方式，“網(wǎng)?！崩锢蠋焼蝹€教你，“同學(xué)”們在交流中互相學(xué)習(xí)，完全沒有在教室里與老師面對面的那種拘束，對中學(xué)生的自由發(fā)揮有很大的幫助。

3、網(wǎng)絡(luò)是加強(qiáng)交流的有益工具。

4、上網(wǎng)的學(xué)生有許多去過聊天室或QQ等其它的交流網(wǎng)站，虛擬的世界里，各自談?wù)撝约合矚g的話題，網(wǎng)友不論老少，不論職業(yè)，只要認(rèn)為興趣相投就可以盡吐心聲。這對渴求朋友，渴求友誼，渴求傾訴的我們是一個絕好的機(jī)會。我們在網(wǎng)絡(luò)中愉快地暢談，得到心靈上的放松和解脫。

消極作用:

1、上網(wǎng)聊天時，由于中學(xué)生的自身特點(diǎn)：對社會的認(rèn)識不深，不能正確的對待社會上的不良現(xiàn)象，自控能力差，對一些不健康的東西容易上癮，從而影響自己的情緒，往往會帶到現(xiàn)實(shí)生活中。這里有一個很好的例子，2月27日中央電視臺焦點(diǎn)訪談播出了新疆經(jīng)濟(jì)電視臺對北京等各大城市網(wǎng)吧的調(diào)查，其中北京某高校附近許多大大小小的網(wǎng)吧形成了網(wǎng)吧一條街，在每天8—9點(diǎn)，網(wǎng)吧就爆滿了，上網(wǎng)的大部分是大學(xué)生和高中生，絕大多數(shù)上網(wǎng)是玩游戲，聊天，容流量大，門外總有人在等待。許多中學(xué)生一坐就是幾個小時，有的一連幾天都不回家，一天24小時連軸轉(zhuǎn)，在網(wǎng)吧里吃住，有的家長一連幾天都找不到自己的孩子，網(wǎng)絡(luò)的誘惑使許多中學(xué)生沉溺其中。

2、由于上網(wǎng)時間長，容易造成對身體的損害。過度沉溺于電腦網(wǎng)絡(luò)中對身體也是一種損害，上網(wǎng)時在電腦前一坐就是幾個小時，只有手指在不停地點(diǎn)，目不轉(zhuǎn)睛地盯著屏幕，對身體健康也是很大傷害的，尤其；是對眼睛的危害，現(xiàn)在我國中學(xué)生原近視率已達(dá)65％，而且有逐年上升的趨勢，所以整天沉溺與網(wǎng)絡(luò)是不可取的，有時上網(wǎng)的愉悅是以金錢和自己身體的健康為代價的。聊天、游戲、造成了學(xué)生成績下降，身心健康受到傷害，不利與中學(xué)生的健康成長。

我們要遵守公約，爭做網(wǎng)絡(luò)道德的規(guī)范。我們要學(xué)習(xí)網(wǎng)絡(luò)道德規(guī)范，懂得基本的對與錯、是與非，增強(qiáng)網(wǎng)絡(luò)道德意識，分清網(wǎng)上善惡美丑的界限，激發(fā)對美好的網(wǎng)絡(luò)生活的向往和追求，形成良好的網(wǎng)絡(luò)道德行為規(guī)范。

我們要遵守公約，爭做網(wǎng)絡(luò)文明的使者。我們要認(rèn)識網(wǎng)絡(luò)文明的內(nèi)涵，懂得崇尚科學(xué)、追求真知的道理，增強(qiáng)網(wǎng)絡(luò)文明意識，使用網(wǎng)絡(luò)文明的語言，在無限寬廣的網(wǎng)絡(luò)天地里倡導(dǎo)文明新風(fēng)，營造健康的網(wǎng)絡(luò)道德環(huán)境。

我們要遵守公約，爭做網(wǎng)絡(luò)安全的衛(wèi)士。我們要了解網(wǎng)絡(luò)安全的重要性，合法、合理地使用網(wǎng)絡(luò)的資源，增強(qiáng)網(wǎng)絡(luò)安全意識，監(jiān)督和防范不安全的隱患，維護(hù)正常的網(wǎng)絡(luò)運(yùn)行秩序，促進(jìn)網(wǎng)絡(luò)的健康發(fā)展。

網(wǎng)絡(luò)在我們面前展示了一幅全新的生活畫面，同時，美好的網(wǎng)絡(luò)生活也需要我們用自己的美德和文明共同創(chuàng)造。讓我們認(rèn)真貫徹《公民道德建設(shè)實(shí)施綱要》的要求，響應(yīng)全國青少年網(wǎng)絡(luò)文明公約的號召，從我做起，從現(xiàn)在做起，自尊、自律，上文明網(wǎng)，文明上網(wǎng)，做一個“文明的網(wǎng)絡(luò)人”。

第五篇：網(wǎng)絡(luò)流構(gòu)圖總結(jié)

網(wǎng)絡(luò)流專題研究

福州一中 肖漢駿

預(yù)備知識(參見Amber論文)網(wǎng)絡(luò)和流

殘留網(wǎng)絡(luò)和增廣路徑 最大流和最小割

主要算法

最大流

增廣路方法 Ford-Fulkerson method 一般增廣路算法 Labeling algorithm 連續(xù)增廣路算法

由陳啟峰提出，競賽中相當(dāng)實(shí)用，近于O(m)容量縮放增廣路算法 Capacity scaling algorithm 最短增廣路算法 Edmonds-Karp algorithm 連續(xù)最短增廣路算法 Successive shortest augmenting path algorithm(Dinic augorithm)預(yù)流推進(jìn)方法Preflow-push method 一般預(yù)流推進(jìn)算法 Generic preflow-push algorithm 先進(jìn)先出預(yù)流推進(jìn)算法 FIFO preflow-push algorithm 最高標(biāo)號預(yù)流推進(jìn)算法 Highest-label preflow-push algorithm(Relabel-to-Front algorithm)最小費(fèi)用流

最小費(fèi)用路方法

一般最小費(fèi)用路算法(SPFA找增廣路，復(fù)雜度近于O(mf)，競賽中實(shí)用)注意：初始流的費(fèi)用必須保證是在所有同流量流中最小的。原始-對偶算法

消圈方法

一般消圈算法 網(wǎng)絡(luò)單純形法

常見變形

多源多匯問題

可通過增添超級源和超級匯解決。

點(diǎn)有容量或費(fèi)用

可以嘗試拆一個點(diǎn)為一入點(diǎn)一出點(diǎn)，將點(diǎn)的限制轉(zhuǎn)移到入點(diǎn)到出點(diǎn)的邊上。

重邊、無向邊和自環(huán)的處理

對于使用邊鏈表存儲的圖，重邊一般不需要特殊處理。但當(dāng)重邊的數(shù)量太多以至于顯著影響算法效率時，可以考慮將相同起點(diǎn)終點(diǎn)的邊的容量相加。

而無向邊則可以看做是在兩個方向上都只要求Flow小于Capa即可。而最小費(fèi)用流問題中的重邊卻反而成為一種處理復(fù)雜權(quán)函數(shù)的手段。根據(jù)題目要求或者問題性質(zhì)，可以為重邊列出一個費(fèi)用隨流量變化的函數(shù)。如果將這個函數(shù)的離散點(diǎn)順次相連，得到的是若干斜率不斷增大的折線段，則可為每段折線段建立一條邊，根據(jù)最小費(fèi)用流的性質(zhì)，重邊選擇的必然是連續(xù)的一段。

給定流值的情況

可以增設(shè)一個源，向原來的源連一條容量為給定流值的邊。

或者在每次增廣的時候，直接將源的可改進(jìn)量設(shè)為到給定流值的差。

或在回溯增廣的時候，將路徑的增廣量同到給定流值的差比較后取小。

有上下界的流問題

注意到下界必須被滿足，可以將所有必要弧抽取，經(jīng)過新建的源和匯。但這時必須為原來的匯到源增添一條容量為無窮大的邊，使之成為滿足流量平衡條件的普通節(jié)點(diǎn)(注意，匯到源的流量實(shí)際上就是原網(wǎng)絡(luò)的流值)。再運(yùn)行最大流算法得到一個可行流。

另一方面，可以先滿足下界，此時有一些點(diǎn)不滿足流量平衡條件。而這可以用多源多匯問題解決。

若求的是最大流，則可以在可行流的基礎(chǔ)上進(jìn)行增廣。

如果求的是最小可行流，則可以通過交換源匯，去除新增的點(diǎn)和邊后運(yùn)行最大流，將多余的流抵消。也可以通過二分匯到源的容量，運(yùn)行可行流。

最大費(fèi)用流

將費(fèi)用取負(fù)，運(yùn)行最小費(fèi)用流算法?；?qū)PFA的大于號反向。

可行最小費(fèi)用流

從T向S連邊，在這基礎(chǔ)上找負(fù)權(quán)圈增廣。分離必要弧，使用最小費(fèi)用流進(jìn)行增廣。

單位容量網(wǎng)絡(luò)流

在構(gòu)圖上，可以利用只有兩種取值的特殊性，容量用true和false表1和0，流量用true表1或-1，用false表0。則可以增廣當(dāng)且僅當(dāng)xor的結(jié)果為true，增廣可以直接變?yōu)橄喾吹牟紶柍Ａ俊?/p>

而單位容量網(wǎng)絡(luò)的另一個重要性質(zhì)是增廣次數(shù)不超過N次。則一般增廣路算法的增廣次數(shù)得以改進(jìn)。

動態(tài)流

可以對時間拆點(diǎn)，建立層次圖處理。

幾個構(gòu)圖的思考方向

流表方案

【例1】 奶牛的新年晚會《算法藝術(shù)與信息學(xué)競賽》p315 注意到奶牛和食物具備“會做”這樣的關(guān)系，且其選擇也只有做1盤與不做兩種。而對每頭奶牛有盤數(shù)限制k，對每種食物也有相應(yīng)的上限值。則二分圖模型呼之欲出。

【例2】 圓桌吃飯問題《算法藝術(shù)與信息學(xué)競賽》p319 注意到幼兒園和桌子有“派出小朋友入座”這樣的關(guān)系，且其選擇也只有派1個與不派兩種。而對幼兒園的人數(shù)和桌子的人數(shù)都有上限值。則也可很容易想到二分圖模型。

【例3】 賽車問題 [2002][金愷]網(wǎng)絡(luò)流應(yīng)用

注意到兩人的賽車均有上場次數(shù)的限制。而每次比賽均是某兩輛車的對決。則就可以建立二分圖模型，利用網(wǎng)絡(luò)流解決。

【例4】 混合圖的歐拉回路《算法藝術(shù)與信息學(xué)競賽》p324 注意到邊和點(diǎn)具有“為點(diǎn)增加入度”的關(guān)系，可以首先統(tǒng)計出每個頂點(diǎn)需要的入度，然后為每個點(diǎn)和邊給出容量限制。

另外一種方法是對混合圖任意定向，然后統(tǒng)計需要反向的邊的個數(shù)。反向邊對于原起點(diǎn)來說增加了入度，對原終點(diǎn)來說了減少入度。如果某點(diǎn)的入度要增加，則可從源向它連邊；如果入度需要減少，則可以向匯連邊。最后只要檢查所有從s出發(fā)或到達(dá)t的邊是否全部滿載。

注意到在這種二分圖上的增廣實(shí)際上在對應(yīng)的原圖中就是找一條路徑，使得頭尾頂點(diǎn)都被改進(jìn)。這便是一種調(diào)整思想。

【例5】 取整矩陣 Yali Train Day12 注意到每個元素只有取下整和取上整兩種選擇，而每行每列對相應(yīng)元素取上整的次數(shù)有上下界。則可以通過求有上下界的最大流解決。

而另一種思想是隨機(jī)確定是取上整還是取下整，再根據(jù)要求進(jìn)行調(diào)整。每次先試圖找一個行列的優(yōu)化方向一致的格子進(jìn)行優(yōu)化。再試圖找一個不滿足條件的格子，將數(shù)值移動到同行/同列的格子中。【例6】 矩陣 CTSC2007 注意到b非0即1。而每行每列對相應(yīng)元素取1的次數(shù)有上下界，則可以通過求有上下界的最大流解決。

而另一種思想是隨機(jī)確定是取上整還是取下整，再根據(jù)要求進(jìn)行調(diào)整。每次先試圖找一個行列的優(yōu)化方向一致的格子進(jìn)行優(yōu)化。再試圖找一個不滿足條件的格子，將數(shù)值移動到同行/同列的格子中。

這實(shí)際上就是利用了增廣過程在原問題中的映射。

【例7】 列車調(diào)度 [2002][金愷]網(wǎng)絡(luò)流應(yīng)用

本題每輛列車只能進(jìn)出站一次，而一旦選擇某輛列車，下一輛可選列車也被確定。此時的一個單位流對應(yīng)的應(yīng)該是一個車道。而點(diǎn)有容量則可以利用拆點(diǎn)法。于是便要解決一個最小費(fèi)用流問題。

【例8】 餐廳問題 [2002][金愷]網(wǎng)絡(luò)流應(yīng)用

本題每天都有對毛巾的需求，而毛巾的來源有多種，去向也有多種，則可以考慮對每天進(jìn)行拆點(diǎn)。此時的一個單位流對應(yīng)的是一條毛巾，由于每天的弧必須被滿足，則是一個有上下界的可行費(fèi)用流問題。

也可以重新構(gòu)圖，直接利用最小費(fèi)用最大流解決。

還可以根據(jù)增廣的特殊性，貪心解決。

常用技巧

注意處理對象以及對象間的關(guān)系。如例1和例2，都提供了3個對象，要仔細(xì)分析具體的限制在哪些對象上，什么對象將另兩個串聯(lián)起來。

注意分析對象身上的限制，可能有多種變形，比如單純的上限，又或是上下界均有。但共同點(diǎn)是相連的邊在兩個對象的計算方式都是一樣的。比如例1中對盤數(shù)的統(tǒng)計，例2中對人數(shù)的統(tǒng)計，是平權(quán)的。挖掘出平權(quán)的計數(shù)關(guān)系，容易分析出什么是點(diǎn)，什么是邊。

割表方案(可參見Amber論文)【例1】 最大密度子圖

結(jié)合01分?jǐn)?shù)規(guī)劃的一般做法，對答案進(jìn)行猜測，轉(zhuǎn)而求解一個最大化問題。

【例2】 最大獲利 NOI2006 首先可以將邊變?yōu)辄c(diǎn)，利用割所具有的性質(zhì)，將邊點(diǎn)依賴關(guān)系用容量為正無窮的邊表示。然后利用最小割這個優(yōu)化工具，從問題反面考慮，計算最小代價。

更優(yōu)的辦法是Amber提出的。注意到邊權(quán)非負(fù)，則可以貪心地選擇點(diǎn)導(dǎo)出子圖。而點(diǎn)導(dǎo)出子圖的權(quán)和不方便計算，可從反面考慮，用S集中的總邊權(quán)和減去割表示。為了利用最小割這個優(yōu)化工具，將每個點(diǎn)連到匯的代價設(shè)為選入S集中的代價，為建設(shè)費(fèi)用，連到源的代價設(shè)為選入T集中的代價，為總邊權(quán)和。而原圖的邊容量可直接設(shè)為邊權(quán)。

【例3】 最優(yōu)壓縮 Yali Train Day4 注意到每個元素只有V0和V1兩種選擇，而權(quán)的計算實(shí)際上對應(yīng)于點(diǎn)的變化以及邊的變化。也就是只有V0與V1之間的邊才計入代價。則容易想到割，并用與源和匯有關(guān)的邊容量處理點(diǎn)權(quán)。

常用技巧

1.2.3.4.不連通。任意一條s-u-v-t路徑都會被割截斷。兩類點(diǎn)。將xor操作變?yōu)楦睢?/p>

用正無窮容量排除不參與決策的邊。

利用與源和匯有關(guān)的邊容量處理點(diǎn)權(quán)。連到匯的容量設(shè)為選入S集中的代價，連到源的容量設(shè)為選入T集中的代價。5.反向思考，充分利用最小割這個優(yōu)化工具。

其他

1.對時間的處理?？梢钥紤]拆點(diǎn)，建立分層圖解決。

2.矩陣類型的題目常常用二分圖進(jìn)行構(gòu)圖。這是由行列以及元素的天然關(guān)系決定的，限制在行列上，由元素將其聯(lián)系在一起。有時也使用奇偶染色構(gòu)圖，此時相鄰關(guān)系是考察重點(diǎn)。有的還要進(jìn)行離散化，例如有障礙棋盤上互不攻擊的車的個數(shù)，就是先對連續(xù)空白段進(jìn)行離散化而得的。

利用特殊性進(jìn)行增廣

【例1】 二分圖匹配問題

由于二分圖匹配問題均是單位流量，且連邊方式十分特殊，可以只存儲Y部節(jié)點(diǎn)的匹配情況，利用CQF式的網(wǎng)絡(luò)流進(jìn)行優(yōu)化。速度非常可觀。

【例2】 剪刀石頭布 WC2007 首先進(jìn)行問題轉(zhuǎn)化：注意到剪刀石頭布情況實(shí)際上對應(yīng)一個長度為3的環(huán)。而非剪刀石頭布情況這對應(yīng)一個拓?fù)涞沫h(huán)，其中有一個頂點(diǎn)有兩條出邊，另一個頂點(diǎn)有兩條入邊。則要求剪刀石頭布情況盡量多，就是要求頂點(diǎn)的入邊平方和盡量小。

于是可以為尚未確定的邊建立節(jié)點(diǎn)，如果邊點(diǎn)存在鄰接關(guān)系，則連接一條邊。點(diǎn)的權(quán)可以用到匯的邊上的費(fèi)用來表示，實(shí)際上是一個凸函數(shù)。這就可以利用重邊的手段處理了。觀察本網(wǎng)絡(luò)的增廣過程，相當(dāng)于選取一條路徑，將其反向，如果解更優(yōu)的話則保留改動。這也就是調(diào)整法的一種實(shí)現(xiàn)了。

【例3】 數(shù)據(jù)備份 APIO2007 首先可以證明選擇的必然是k條邊數(shù)為1的線段，而要求權(quán)和最小。這顯然是一個最小費(fèi)用最大流問題。但本題數(shù)據(jù)規(guī)模極大，必須另找方法。

注意到每次進(jìn)行增廣的時候，或者是直接添加一條長度為1的線段?；蚴菍⑦B續(xù)交錯的線段全部反向，則一旦形成連續(xù)交錯線段，就不會改變。

這可以使用映射堆進(jìn)行優(yōu)化。每次刪除一個權(quán)最小的線段，并將前后線段刪除，把當(dāng)前線段的權(quán)修改為前后線段的和減去當(dāng)前線段的權(quán)即可。

其他

對于一些有向圖的問題，由于增廣路的特殊性，調(diào)整方法往往是對一條鏈反向。分析時可以緊抓入度或緊抓出度，結(jié)合一起分析反而增大難度。

對每個元素有兩種選擇的問題，可以嘗試任意選擇一種，再根據(jù)限制進(jìn)行構(gòu)圖。