最大流演算法
❶ edmonds-karp演算法是如何求最大流的
Edmonds-Karp 演算法步驟
每次通過BFS，找到殘余網路上從源點到匯點的一條最短增廣路
在流網路上增加增廣路
修改殘余網路，殘余容量減去增廣路，並添加增廣路的反向弧
當無法BFS到增廣路時，演算法結束
USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: ditch
LANG: C++
//對ford演算法的改進，變為多項試的。
/*
ID:cmykrgb1
PROG:ditch
LANG:C++
*/
#include<iostream>
#include<fstream>
#defineMAX201
usingnamespacestd;
classTadjl
{
public:
classTnode
{
public:
intr,v;
voidset(inttr,inttv)
{
r=tr;
v=tv;
}
};
intcnt;
Tnodelink[MAX];
};
classtQueue
{
public:
classlinklist
{
public:
linklist*next;
intvalue;
linklist()
{
next=0;
value=0;
}
};
linklist*first,*last;
intsize;
voidadd(intp)
{
if(size==0)
first=last=newlinklist;
else
last=last->next=newlinklist;
last->value=p;
size++;
}
intdel()
{
intrtn=first->value;
linklist*tfirst=first;
first=first->next;
deletetfirst;
size--;
returnrtn;
}
voidreset()
{
size=0;
first=last=0;
}
tQueue()
{
reset();
}
};
ifstreamfi("ditch.in");
ofstreamfo("ditch.out");
Tadjladjl[MAX];
intN,M,ans;
inlineintmin(inta,intb)
{
returna<b?a:b;
}
voidinit()
{
inti,a,b,v;
fi>>N>>M;
for(i=1;i<=N;i++)
{
fi>>a>>b>>v;
adjl[a].link[++adjl[a].cnt].set(b,v);
}
}
intedmonds(intstart,intend)
{
inti,j,k;
intfather[MAX],fp[MAX],max[MAX];
intMaxflow=0;
memset(father,0,sizeof(father));
max[start]=0x7FFFFFFF;
tQueue*Q=newtQueue;
Q->add(start);
while(Q->size)
{
i=Q->del();
for(k=1;k<=adjl[i].cnt;k++)
{
j=adjl[i].link[k].r;
if(!adjl[i].link[k].v||j==start)continue;
if(!father[j])
{
father[j]=i;
fp[j]=k;
max[j]=min(adjl[i].link[k].v,max[i]);
if(j==end)
{
Maxflow+=max[j];
while(father[j])
{
adjl[father[j]].link[fp[j]].v-=max[end];
adjl[j].link[++adjl[j].cnt].set(father[j],max[j]);
j=father[j];
}
memset(father,0,sizeof(father));
Q->reset();
Q->add(start);
break;
}
Q->add(j);
}
}
}
returnMaxflow;
}
voidprint()
{
fo<<ans<<endl;
fi.close();
fo.close();
}
intmain()
{
init();
ans=edmonds(1,M);
print();
return0;
}
❷ 請問求最大流的時間復雜度最小的演算法是哪一種
理論上是最高標號預流推進,英語縮寫HLPP
但是實現較復雜
實踐發現你把dinic和sap學了應該不會出先這兩種都過不去的程序設計題目,要注意sap的優化
❸ 運籌學網路最大流標記演算法的理論依據是什麼
運籌學網路最大流標記演算法的理論依據是？運籌帷幄。
❹ 最大流量計算
你得知道通過管道的速度，然後截面積乘以速度再乘以60秒，這就是每分鍾的最大流量
❺ 網路流的最大流演算法
1、augment path，直譯為「增廣路徑」，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個演算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個演算法必然會結束。
尋找通路的時候可以用DFS，BFS最短路等演算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個復雜得多的演算法，就是預推進演算法。
2、push label，直譯為「預推進」演算法。
3、壓入與重標記(Push-Relabel)演算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的演算法外，還有一種求最大流的演算法被稱為壓入與重標記(Push-Relabel)演算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流盡可能多的壓向終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的演算法普遍要比Ford-Fulkerson系的演算法快，但是缺點是相對難以理解。
Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。演算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鏈表裡，從鏈表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鏈表的頭部，對下一個頂點開始Discharge。
Relabel-to-Front演算法的時間復雜度是O(V^3)，還有一個叫Highest Label Preflow Push的演算法復雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的演算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
Push-Relabel類的演算法有一個名為gap heuristic的優化，就是當存在一個整數0<k<V，沒有任何頂點滿足h[v]=k時，對所有h[v]>k的頂點v做更新，若它小於V+1就置為V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#;inttt,kase;intnn,m;intH[45],X[1004],P[1004],flow[1004],tot,cap[1005];intd[45];intS,T;voidadd(intx,inty,intz){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int>q;boolbfs(){memset(d,0,sizeof(d));d[S]=1;intx;q.push(S);while(!q.empty()){x=q.front();q.pop();for(inti=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}intdfs(intx,inta){if(x==T||a==0)returna;intf=a,tmp;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;returnf-a;}intDinic(){intf=0;while(bfs())f+=dfs(S,inf);returnf;}intmain(){/**輸入過程省略**/intmaxflow=Dinic();printf(%d
,maxflow);return0;}
❻ 求二分圖最大匹配的最大流演算法，附Pascal程序
program bgf;
const maxn=402;
var map:array[1..maxn,1..maxn]of longint;
hash:array[1..maxn]of boolean;
n,m,ans:longint;
procere init;
var i,j,x,s:longint;
begin
readln(n,m);
fillchar(map,sizeof(map),0);
for i:=2 to n+1 do map[1,i]:=1;
for i:=1 to n do
begin
read(s);
for j:=1 to s do
begin
read(x);
map[i+1,x+n+1]:=1;
end;{for}
readln;
end;{for}
for i:=n+2 to n+m+1 do map[i,n+m+2]:=1;
n:=n+m+2;
end;{init}
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;{min}
function DFS(u,low:longint):longint;
var i,num:longint;
begin
if u=n then exit(low);
if hash[u] then exit(0);
hash[u]:=true;
for i:=1 to n do
if (map[u,i]>0)and(not hash[i]) then
begin
num:=DFS(i,min(low,map[u,i]));
if num>0 then
begin
dec(map[u,i],num);
inc(map[i,u],num);
exit(num);
end;{if}
end;{if}
exit(0);
end;{DFS}
procere calc;
var flow:longint;
begin
ans:=0;
repeat
fillchar(hash,sizeof(hash),0);
flow:=DFS(1,maxint);
if flow>0 then ans:=ans+flow;
until flow<=0;
end;{calc}
procere print;
begin
writeln(ans);
end;{print}
begin{main}
init;
calc;
print;
end.
❼ c/c++ 最大流演算法ford-fulkerson
你的問題是用C/C++寫最大流演算法ford-fulkerson演算法。頂點就是節點。
void maximum_flow(int n, int s, int t, int *capacity, int *flow)
可以參考：演算法模板-最大流（Ford-fulkerson演算法）
❽ 求平面圖最大流演算法
對於一個s-t平面圖，我們對其進行如下改造：
1.n連接s和t，得到一個附加面
2.求該圖的對偶圖G*：令附加面對應的點為s*，無界面對應的點為t*
3.刪去s*和t*之間的邊
一條從s*到t*的路徑，就對應了一個s-t割！
更進一步，如果我們令每條邊的長度等於它的容量，那麼最小割的容量就等於最短路的長度！
分析一下時間復雜度n新圖中的點數和邊數都是O(n)的n使用二叉堆優化的Dijkstra演算法求最短路，時間復雜度為O(nlog2n)