一．Ford和Fulkerson迭加算法.
基本思路：把各條弧上單位流量的費(fèi)用看成某種長度,用求解最短路問題的方法確定一條自V1至Vn的最短路;在將這條最短路作為可擴(kuò)充路,用求解最大流問題的方法將其上的流量增至最大可能值;而這條最短路上的流量增加后,其上各條弧的單位流量的費(fèi)用要重新確定,如此多次迭代,最終得到最小費(fèi)用最大流.
迭加算法：
1) 給定目標(biāo)流量F或∞,給定最小費(fèi)用的初始可行流=0
2) 若V(f)=F,停止,f為最小費(fèi)用流;否則轉(zhuǎn)(3).
3) 構(gòu)造 相應(yīng)的新的費(fèi)用有向圖W(fij),在W(fij)尋找Vs到Vt的最小費(fèi)用有向路P(最短路),沿P增加流f的流量直到F,轉(zhuǎn)(2);若不存在從Vs到Vt的最小費(fèi)用的有向路P,停止.f就是最小費(fèi)用最大流.
具體解題步驟：
設(shè)圖中雙線所示路徑為最短路徑，費(fèi)用有向圖為W（fij）．
在圖(a)中給出零流 f,在圖(b)中找到最小費(fèi)用有向路,修改圖(a)中的可行流,δ=min{4,3,5}=3,得圖(c),再做出(c)的調(diào)整容量圖,再構(gòu)造相應(yīng)的新的最小費(fèi)用有向路得圖(d), 修改圖(c)中的可行流, δ=min{1,1,2,2}=1,得圖(e),以此類推,一直得到圖(h),在圖(h)中以無最小費(fèi)用有向路,停止,經(jīng)計(jì)算:
圖(h)中 最小費(fèi)用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
圖(g)中 最大流=5
最大流問題僅注意網(wǎng)絡(luò)流的流通能力，沒有考慮流通的費(fèi)用。實(shí)際上費(fèi)用因素是很重要的。例如在交通運(yùn)輸問題中，往往要求在完成運(yùn)輸任務(wù)的前提下，尋求一個(gè)使總運(yùn)輸費(fèi)用最省的運(yùn)輸方案，這就是最小費(fèi)用流問題。如果只考慮單位貨物的運(yùn)輸費(fèi)用，那么這個(gè)問題就變成最短路問題。由此可見，最短路問題是最小費(fèi)用流問題的基礎(chǔ)。現(xiàn)已有一系列求最短路的成功方法。最小費(fèi)用流(或最小費(fèi)用最大流)問題 ，可以交替使用求解最大流和最短路兩種方法，通過迭代得到解決。
//老老實(shí)實(shí)看了一天的書，終于敲出了第一個(gè)關(guān)于網(wǎng)絡(luò)流的程序
//慶祝流的零的突破
#include<iostream>
using namespace std;
int n,np,nc,m,flag,res;
int arr[110][110];
int q[10000],pre[10000],used[110];
int path(int s)
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head<tail)
{ temp=tail;
for(i=head;i<temp;i++)
{ u=q[i];
if(u==n+1)
return 1;
for(j=0;j<=n+1;j++)
if(!used[j] && arr[u][j]>0)
{pre[j]=u;
used[j]=1;
q[tail++]=j;
}
}
head=temp;
}
return 0;
}
void ford_fulkerson()
{ int i,j,u,v,min;
min=INT_MAX;
u=pre[n+1];
v=n+1;
while(u>=0)
{if(arr[u][v]<min)
min=arr[u][v];
v=u;
u=pre[u];
}
u=pre[n+1];
v=n+1;
while(u>=0)
{ arr[u][v]=arr[u][v]-min;
arr[v][u]=arr[v][u]+min;
v=u;
u=pre[u];
}
res=res+min;
}
int main()
{int u,v,w,i,j;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d%d%d",&n,&np,&nc,&m))!=EOF)
{ flag=0;
res=0;
memset(arr,0,sizeof(arr));
for(i=0;i<m;i++)
{ while(getchar()!='(');
scanf("%d,%d)%d",&u,&v,&w);
arr[u][v]=w;
}
for(i=0;i<np;i++)
{ while(getchar()!='(');
scanf("%d)%d",&v,&w);
arr[n][v]=w;
}
for(i=0;i<nc;i++)
{ while(getchar()!='(');
scanf("%d)%d",&u,&w);
arr[u][n+1]=w;
}
while(!flag)
{ memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
if(path(n))
ford_fulkerson();
else
flag=1;
}
printf("%d\n",res);
}
return 0;
}