[cpp] /*************************************************** 算法引入： 任何容量網絡的最大流流量是唯一且確定的，但是它的最大流f並不是唯一的; 既然最大流f不唯一，因此，如果每條弧上不僅有容量限制，還有費用r; 即每條弧上有一個單位費用的參數，那麼在保證最大流的前提下; 還存在一個選擇費用最小的最大流問題，即為最小費用最大流問題; 算法思想： 尋找最大流的方法是從某個可行流出發，找到關於這個流的一條增廣路P; 沿著P調整f，對新的可行流又試圖尋找關於它的增廣路，循環直至不存在增廣路為止; 要求最小費用最大流： 如果f是流量為f1的可行流中費用最小者，而p是關於f的所有增廣路中費用最小的增廣路; 那麼沿著p去調整f，得到可行流_f，就是流量為f1的所有可行流中的費用最小者; 這樣當f是最大流時，它也就是所要求的最小費用最大流了; 算法內容： 在尋找關於f的最小費用增廣路的過程中; 需要構造一個關於f的伴隨網絡W(f); www.2cto.com 把在原網絡中尋找關於f的最小費用增廣路轉換為在伴隨網絡W(f)中尋找從Vs到Vt的最短路問題; 其中伴隨網絡W(f)構造為： 頂點為原網絡中的頂點; www.2cto.com 原網絡中的每條弧<u,v>變成兩個方向相反的弧<u,v>和<v,u>; 在W(f)中每條弧<u,v>的權值為： if(f(u,v)<c(u,v)) W(u,v)=r(u,v); else if(f(u,v)==c(u,v)) W(u,v)=無窮大(可省略); if(f(u,v)>0) W(v,u)=-r(u,v); else if(f(u,v)==0) W(v,u)=無窮大(可省略); 算法流程： ①開始取f(0)={0}; ②一般若在第k-1步得到的最小費用流為f(k-1),則構造伴隨網絡W(f(k-1)); ③在W(f(k-1))中尋找從Vs到Vt的最短路，若不存在則轉⑤，存在轉④; ④在原網絡G中得到相應的增廣路P，在P上對f(k-1)進行調整;調整後新的可行流為f(k)，轉②; ⑤f(k-1)為最小費用最大流，算法完畢; 算法測試： HDU1533,ZOJ2404,POJ2195(Going Home); 題意： 在一個網絡地圖上，有n個小人和n棟房子; 在每個單位時間內，每個人可以往水平方向或垂直方向移動一步，走到相鄰的方格中; 對於每個小人，走一步需支付一美元，直到他走入房子裡，且每棟房子只能容納一個人; 求讓n個小人移動到n個不同的房子，求需要支付的最小費用; ****************************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> #include<queue> using namespace std; int n,m; const int N=250; const int M=10000; const int MAX=0xffffff; char coord[N][N];//坐標集 int pre[M];//存儲前驅頂點 int dist[M];//存儲到源點s的距離 int inq[M];//每個頂點是否在隊列中的標志 int min_c_f;//記錄增廣路徑中的殘留容量 int vertex;//頂點數 int sum;//保存最小費用 struct element { int c;//容量 int f;//流 int c_f;//殘留容量 int v;//價值 } G[N][N]; struct man//記錄小矮人的坐標 { int x,y; } man[N]; struct house//記錄房子的坐標 { int x,y; } house[N]; void init() { sum=0; int mcase,hcase;//記錄有多少個小矮人和房子 mcase=hcase=0; for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { cin>>coord[i][j]; if(coord[i][j]=='m')//記錄小矮人的坐標 { mcase++; man[mcase].x=i; man[mcase].y=j; } if(coord[i][j]=='H')//記錄房子的坐標 { hcase++; house[hcase].x=i; house[hcase].y=j; } } } vertex=mcase+hcase+1;//加入超源點0和超匯點，注意要+1，即抽象成網絡流的結構 for(int u=0; u<=vertex; u++)//初始流為0，所以不用重構W(f); { for(int v=0; v<=vertex; v++) { G[u][v].c=G[v][u].c=0; G[u][v].c_f=G[v][u].c_f=0; G[u][v].f=G[v][u].f=0; G[u][v].v=G[v][u].v=MAX; } } for(int i=1; i<=mcase; i++) { G[0][i].v=0;//從超源點到各個小矮人之間的權值取為0 G[0][i].c=G[0][i].c_f=1;//從超源點到各個小矮人之間的容量取為1 for(int j=1; j<=hcase; j++) { int w=abs(house[j].x-man[i].x)+abs(house[j].y-man[i].y);//計算小矮人到每一個房子之間的距離 G[i][mcase+j].v=w;//將距離賦給對應的權值，注意第二個下標，即表示房子的下標為mcase+j~！！ G[i][mcase+j].c=1;//容量取為1 G[i][mcase+j].c_f=G[i][mcase+j].c; G[mcase+j][vertex].v=0;//將從各個房子到超匯點之間的權值取為0，注意房子的下標為mcase+j G[mcase+j][vertex].c=G[mcase+j][vertex].c_f=1;//將從各個房子到超匯點之間的容量取為0，注意房子的下標為mcase+j } } } void SPFA(int s)//求最短路徑的SPFA算法 { queue<int> Q; int u; for(int i=0; i<=vertex; i++)//初始化 { dist[i]=MAX; pre[i]=-1; inq[i]=0; } dist[s]=0; Q.push(s); inq[s] = 1; while(!Q.empty()) { u=Q.front(); Q.pop(); inq[u]=0; for(int i=0; i<=vertex; i++)//更新u的鄰接點的dist[], pre[], inq[] { int v=i; if(G[u][v].c_f==0) // 表示(u,v)沒有邊 continue; if(G[u][v].v==MAX) G[u][v].v=-G[v][u].v; if(dist[v]>dist[u]+G[u][v].v)//松弛操作 { dist[v]=dist[u]+G[u][v].v; pre[v]=u; if(inq[v]==0) { Q.push(v); inq[v]=1; } } } } } void ford_fulkerson(int s,int t) { SPFA(s); while(pre[t]!=-1)//pre為-1表示沒有找到從s到t的增廣路徑 { //cout<<dist[t]<<"^_^"<<endl; sum+=dist[t];//將這一條最短路徑的值加進sum min_c_f=MAX; int u=pre[t], v=t;//計算增廣路徑上的殘留容量 while(u!=-1) { if(min_c_f > G[u][v].c_f) min_c_f=G[u][v].c_f; v=u; u=pre[v]; } u=pre[t], v=t; while(u!=-1) { G[u][v].f+=min_c_f; //修改流 G[v][u].f=-G[u][v].f; G[u][v].c_f=G[u][v].c-G[u][v].f; //修改殘留容量 G[v][u].c_f=G[v][u].c-G[v][u].f; v=u; u=pre[v]; } SPFA(s); } } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); while(cin>>m>>n,m||n) { init(); ford_fulkerson(0,vertex);//計算從超源點0到超匯點vertex之間的最小費用最大流 cout<<sum<<endl; } return 0; }
