#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> using namespace std; const int N = 10; const int MAX = 0xfffffff; int n,m;//n是點數(shù)，m是邊數(shù) int source, sink;//source為源點，sink為匯點 /**************************************************************** 最大流算法--EK算法 算法分析： 最大流EK算法的基本思想是在網(wǎng)絡(luò)中找增廣路徑； 找到一條增廣路徑就計算這條路徑可已通過的最大流； 即瓶頸邊的容量。 然后修改這條路徑上的每條邊的容量； 如果在路徑上就減去剛求出來的流量加上流量其他的邊的容量不變； 然后在這個殘留網(wǎng)路上再搜一條增廣路徑，直到?jīng)]有增廣路徑為止。 *****************************************************************/ int map[N][N] , pre1[N];//map為網(wǎng)路，pre1為每個點的前驅(qū) bool vist[N];//標(biāo)志一個點是否被訪問 bool EKBfs()//搜索增廣路徑 { queue<int>Q; memset(pre1 , -1 , sizeof(pre1)); memset(vist , false , sizeof(vist)); Q.push(source);//先將源點壓入隊列 vist[source] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); if(u == sink) return true;//找到一條增廣路徑 for(int v = 1 ; v <= n ; v++) { if(map[u][v] && !vist[v])//邊存在且v沒被訪問 { vist[v] = true; pre1[v] = u; Q.push(v); } } } return false;//沒找到增廣路徑 } int EK() { int maxFlow = 0 , minf;//minf為找到增廣路徑后路徑上可以通過的最大流量 while(EKBfs()) { minf = MAX; int v = sink; while(pre1[v] != -1)//從從匯點到源點找瓶頸邊 { minf = min(minf , map[pre1[v]][v]); v = pre1[v]; } maxFlow += minf;//最大流加上剛找到的流量 v = sink; while(pre1[v] != -1)//修改這條路上的容量 { int u = pre1[v]; map[u][v] -= minf; map[v][u] += minf; v = u; } } return maxFlow; } /**************************************************************** 最大流算法--SAP算法 算法分析： SAP算法也是每次都找一條從源點到匯點的增廣路徑; 只不過在找到一條增廣路徑之后并不是又從源點開始; 而是從當(dāng)前找到的增廣路徑的瓶頸邊往下找期望一次找到更多的邊來減少搜索的時間。 再就是這個算法吸收的壓入與重標(biāo)記算法的頂點標(biāo)號的方法； 給每個點一個標(biāo)號，源點的標(biāo)號最大不超過頂點的數(shù)量； 因為一條簡單路徑n個點最多只含n-1條邊； 那么頂點標(biāo)號實質(zhì)就是從這個點出發(fā)到匯點要走的邊的最少的數(shù)量。 當(dāng)有邊且h[u]=h[v]+1時我們稱這條邊是一條可行邊； 每次找增廣路徑都沿著可行邊； 當(dāng)從某個點出發(fā)沒有找到可行邊就把這個點的標(biāo)號標(biāo)記為它的最小子點標(biāo)號加一； 這樣標(biāo)號是一直增加的當(dāng)有某個標(biāo)號的的點的數(shù)量為0時； 這時不管在怎么找也不會有增廣路徑了僅退出計算。 *****************************************************************/ struct Edge2//邊的數(shù)據(jù)結(jié)構(gòu)，c為邊的容量 { int v , c , next; } edge2[25]; int head2[10] , pre2[10];//pre2為每個點的前驅(qū) //curEdge為從每個點出發(fā)的可行邊的存儲位置，high為每個點的高度標(biāo)號，hNum為相應(yīng)標(biāo)號點的數(shù)量 int curEdge[10] , high[10] , hNum[10]; void addedge(int u , int v , int c , int &num2)//增加一條邊，及其反向邊 { edge2[num2].c = c; edge2[num2].v = v; edge2[num2].next = head2[u]; head2[u] = num2++; edge2[num2].c = 0; edge2[num2].v = u; edge2[num2].next = head2[v]; head2[v] = num2++; } int SAP()//最大流SAP算法 { int maxFlow = 0;//最大流 memset(high , 0 , sizeof(high));//初始化 memset(hNum , 0 , sizeof(hNum)); memset(pre2 , -1 , sizeof(pre2)); for(int i = 1 ; i <= n ; i++)//把當(dāng)前邊置為每個點的第一條邊 curEdge[i] = head2[i]; hNum[0] = n;//高度為0的點的數(shù)量為n int u = source; while(high[source] < n) { if(u == sink)//當(dāng)前為匯點說明找到一條增廣路徑 { int minf = MAX , neck; //從源點出發(fā)沿增廣路徑找瓶頸邊 for(int k = source ; k != sink ; k = edge2[curEdge[k]].v) { if(minf > edge2[curEdge[k]].c) { neck = k; minf = edge2[curEdge[k]].c; } } //從源點出發(fā)把增廣路徑上的邊的容量及其反向邊的容量修改 for(int k = source ; k != sink ; k = edge2[curEdge[k]].v) { int tmp = curEdge[k]; edge2[tmp].c -= minf; edge2[tmp^1].c += minf; } //最大流加上新增加的流 maxFlow += minf; u = neck;//下次從瓶頸邊開始找增廣路徑 } //找從當(dāng)前點出發(fā)的可行邊 int k = curEdge[u]; for(; k != -1 ; k = edge2[k].next) { if(edge2[k].c && high[u] == high[edge2[k].v]+1) break; } if(k != -1)//找到可行邊 { curEdge[u] = k;//將當(dāng)前點出發(fā)的可行邊的位置修改 pre2[edge2[k].v] = u; u = edge2[k].v;//下次從可行邊的下一個點搜索 } else//沒找到可行邊 { //當(dāng)前點的標(biāo)號要修改，所以先把對應(yīng)的數(shù)量減一，如果為0就退出計算 if(--hNum[high[u]] == 0) break; curEdge[u] = head2[u];//把可行邊記為第一條邊 int tmp = n ; //找從當(dāng)前點出發(fā)標(biāo)號最小的點的標(biāo)號 for(int k = head2[u] ; k != -1 ; k = edge2[k].next) { if(edge2[k].c) tmp = min(tmp , high[edge2[k].v]); } high[u] = tmp+1;//修改當(dāng)前點的標(biāo)號 hNum[high[u]]++; if(u != source) u = pre2[u];//從當(dāng)前點出發(fā)沒有增廣路，從其父結(jié)點開始搜 } } return maxFlow; } /**************************************************************** 最大流算法--Dinic算法 算法分析： Dinic算法和SAP算法有異曲同工之妙，它把殘留網(wǎng)路變成分層網(wǎng)絡(luò); 每次尋找都找最短的路徑去增廣。 在殘留網(wǎng)絡(luò)上每個點都有一個層編號; 每次都按照level[v]=level[u]+1的邊增廣。 如果在殘留網(wǎng)絡(luò)里對每個點編號時無法對匯點編號; 則說明已經(jīng)沒有增廣路了。 *****************************************************************/ struct Edge3 { int v , c , next; } edge3[25]; //level為每個點的層數(shù)編號 int head3[10] , level[10]; void addEdge(int u , int v , int c , int &num3)//添加一條邊 { edge3[num3].v = v; edge3[num3].c = c; edge3[num3].next = head3[u]; head3[u] = num3++; edge3[num3].c = 0; edge3[num3].v = u; edge3[num3].next = head3[v]; head3[v] = num3++; } bool searchLevel()//用bfs對每個點編號 { memset(level , -1 , sizeof(level)); queue<int>Q; Q.push(source); level[source] = 0; while(!Q.empty()) { int u = Q.front(); if(u == sink) return true; Q.pop(); for(int k = head3[u] ; k != -1 ; k = edge3[k].next) { int v = edge3[k].v; if(edge3[k].c && level[v] == -1) { level[v] = level[u]+1; Q.push(v); } } } return false; } int DinicDfs(int u , int minf) { //minf為當(dāng)前增廣路徑中瓶頸邊的容量 if(u == sink) return minf; int ret = 0;//從當(dāng)前這個點出發(fā)找到的所有流量之和 for(int k = head3[u] ; k != -1 ; k = edge3[k].next) { int v = edge3[k].v; if(edge3[k].c && level[v] == level[u]+1) { //min(minf-ret , edge1[k].c)的意思是修改增廣路徑中瓶頸邊的容量 int f = DinicDfs(v , min(minf-ret , edge3[k].c)); edge3[k].c -= f; edge3[k^1].c += f; ret +=f; //瓶頸邊的容量被消耗殆盡說明從當(dāng)前點出發(fā)沒有增廣路了，要回朔 if(ret == minf) return ret; } } return ret; } int Dinic() { int maxFlow = 0; while(searchLevel())//殘留網(wǎng)絡(luò)還可以分層說明從源點到匯點還可以找增廣路徑 { maxFlow += DinicDfs(source , MAX); } return maxFlow; } /**************************************************************** 附測試數(shù)據(jù)： 6 10 1 2 16 1 3 13 2 3 10 2 4 12 3 2 4 3 5 14 4 3 9 5 4 7 5 6 4 4 6 20 （算法導(dǎo)論Page405） *****************************************************************/ int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); while(cin>>n>>m) { for(int i = 1 ; i <= n ; i++)//初始化 for(int j = 1 ; j <= n ; j++) map[i][j] = 0; memset(head2 , -1 , sizeof(head2)); memset(head3 , -1 , sizeof(head3)); for(int i = 0 , num2 = 0 , num3 = 0; i < m ; i++) { int u,v,c; cin>>u>>v>>c; map[u][v] = c;//EK addedge(u , v , c , num2);//SAP addEdge(u , v , c , num3);//Dinic } source = 1 , sink = 6; int max_flow1 = EK(); int max_flow2 = SAP(); int max_flow3 = Dinic(); cout<<"max_flow1=="<<max_flow1<<endl; cout<<"max_flow2=="<<max_flow2<<endl; cout<<"max_flow3=="<<max_flow3<<endl; } return 0; }

總結(jié)

以上是生活随笔為你收集整理的网络最大流的三种基础算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。