求網(wǎng)絡(luò)的最小費(fèi)用最大流-C語言  您要打印的文件是：求網(wǎng)絡(luò)的最小費(fèi)用最大流-C語言  打印本文


      求網(wǎng)絡(luò)的最小費(fèi)用最大流-C語言



      作者：云嫣    轉(zhuǎn)貼自：數(shù)海


             
            求網(wǎng)絡(luò)的最小費(fèi)用最大流 





            求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁的數(shù)字是容量(運(yùn)費(fèi))。



            一．Ford和Fulkerson迭加算法.
            基本思路：把各條弧上單位流量的費(fèi)用看成某種長度,用求解最短路問題的方法確定一條自V1至Vn的最短路;在將這條最短路作為可擴(kuò)充路,用求解最大流問題的方法將其上的流量增至最大可能值;而這條最短路上的流量增加后,其上各條弧的單位流量的費(fèi)用要重新確定,如此多次迭代,最終得到最小費(fèi)用最大流.
            迭加算法：
            1) 給定目標(biāo)流量F或∞,給定最小費(fèi)用的初始可行流{fij}=0
            2) 若V(f)=F,停止,f為最小費(fèi)用流;否則轉(zhuǎn)(3).
            3) 構(gòu)造{fij} 
            相應(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)計算:
            圖(h)中 最小費(fèi)用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
            圖(g)中 最大流=5 
            C語言程序如下(運(yùn)行通過):
            /*Ford和Fulkerson迭加算法*/
            #include"stdio.h"
            void main()
            {int a,b,i,j,k,p,n,B[10][10],C[10][10],D[10][10],P[10][10][10];
            printf("please input n:\n");
            scanf("%d",&n);
            printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            scanf("%7d,%7d",&C[i][j],&B[i][j]); 
//輸入各點(diǎn)(i,j)之間的容量C[i][j]和運(yùn)費(fèi)B[i][j]
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            {D[i][j]=B[i][j];
            for(k=0;k<=n;k++)
            P[i][j][k]=0;
            if(D[i][j]<100) //注：100表示Vi到Vj之間無可行路
            {P[i][j][i]=1;P[i][j][j]=1;}
            }
            for(k=0;k<=n;k++)
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            if(D[i][k]+D[k][j]<D[i][j])
            {D[i][j]=D[i][k]+D[k][j];
            for(p=0;p<=n;p++)
            P[i][j][p]=P[i][k][p]||P[k][j][p];
            } //調(diào)用FLOYD算法
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            } //由表D中的數(shù)值確定V0到V5的最短路
            a=C[1][3];b=B[1][3]*D[0][5];
            printf("a=%d,b=%d\n",a,b);
            B[1][3]=100; //將容量已滿的路改為不可行路
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            {D[i][j]=B[i][j];
            for(k=0;k<=n;k++)
            P[i][j][k]=0;
            if(D[i][j]<100)
            {P[i][j][i]=1;P[i][j][j]=1;}
            }
            for(k=0;k<=n;k++)
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            if(D[i][k]+D[k][j]<D[i][j])
            {D[i][j]=D[i][k]+D[k][j];
            for(p=0;p<=n;p++)
            P[i][j][p]=P[i][k][p]||P[k][j][p];
            } //調(diào)用FLOYD算法
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            } //由表D中的數(shù)值確定V0到V5的新最短路
            a=a+C[1][2];b=b+D[0][5];
            printf("a=%d,b=%d\n",a,b);
            B[0][1]=100;B[1][2]=100;B[4][3]=100; //將容量已滿的路改為不可行路
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            {D[i][j]=B[i][j];
            for(k=0;k<=n;k++)
            P[i][j][k]=0;
            if(D[i][j]<100)
            {P[i][j][i]=1;P[i][j][j]=1;}
            }
            for(k=0;k<=n;k++)
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            if(D[i][k]+D[k][j]<D[i][j])
            {D[i][j]=D[i][k]+D[k][j];
            for(p=0;p<=n;p++)
            P[i][j][p]=P[i][k][p]||P[k][j][p];
            } //調(diào)用FLOYD算法
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            } //由表D中的數(shù)值確定V0到V5的新最短路
            a=a+C[2][4]-C[4][3];b=b+D[0][5];
            printf("a=%d,b=%d\n",a,b);
            B[2][4]=100; //將容量已滿的路改為不可行路
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            {D[i][j]=B[i][j];
            for(k=0;k<=n;k++)
            P[i][j][k]=0;
            if(D[i][j]<100)
            {P[i][j][i]=1;P[i][j][j]=1;}
            }
            for(k=0;k<=n;k++)
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            if(D[i][k]+D[k][j]<D[i][j])
            {D[i][j]=D[i][k]+D[k][j];
            for(p=0;p<=n;p++)
            P[i][j][p]=P[i][k][p]||P[k][j][p];
            } //調(diào)用FLOYD算法
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            } //檢驗有無V0到V5的新最短路
            }

            運(yùn)行結(jié)果:
            please input n:
            5
            please input C[5][5],B[5][5]:
            0,0 4,1 5,3 0,100 0,100 0,100
            0,100 0,0 1,1 3,3 0,100 0,100
            0,100 0,100 0,0 0,100 2,4 0,100
            0,100 0,100 0,100 0,0 0,100 5,2
            0,100 0,100 0,100 1,1 0,0 2,4
            0,100 0,100 0,100 0,100 0,100 0,0
            D[5][5]:
            0 1 2 4 6 6
            100 0 1 3 5 5
            100 100 0 5 4 7
            100 100 100 0 100 2
            100 100 100 1 0 3
            100 100 100 100 100 0
            a=3,b=18
            D[5][5]:
            0 1 2 7 6 9
            100 0 1 6 5 8
            100 100 0 5 4 7
            100 100 100 0 100 2
            100 100 100 1 0 3
            100 100 100 100 100 0
            a=4,b=27
            D[5][5]:
            0 100 3 100 7 11
            100 0 100 100 100 100
            100 100 0 100 4 8
            100 100 100 0 100 2
            100 100 100 100 0 4
            100 100 100 100 100 0
            a=5,b=38
            D[5][5]:
            0 100 3 100 100 100
            100 0 100 100 100 100
            100 100 0 100 100 100
            100 100 100 0 100 2
            100 100 100 100 0 4
            100 100 100 100 100 0
            //注：100表示Vi到Vj之間無可行路
            　
            二．圈算法：
            1) 利用Ford和Fulkson標(biāo)號算法找出流量為F(<=最大流)的流f.
            2) 構(gòu)造f對應(yīng)的調(diào)整容量的流網(wǎng)絡(luò)N'(f).
            3) 搜索N'(f)中的負(fù)費(fèi)用有向圖C(Floyd算法),若沒有則停止,否則轉(zhuǎn)(4).
            4) 在C上找出最大的循環(huán)流,并加到N上去,同時修改N'(F)中C的容量,轉(zhuǎn)(3).
            具體解題步驟:

            利用Ford和Fulkson標(biāo)號算法,得網(wǎng)絡(luò)的最大流F=5,見圖(a),由圖(a)構(gòu)造相應(yīng)的調(diào)整容量的流網(wǎng)絡(luò)(b),圖(b)中不存在負(fù)費(fèi)用有向圖,故停止．經(jīng)計算:
            圖(b)中 最小費(fèi)用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38
            圖(a)中 最大流為F=5
            　
            C語言程序如下(運(yùn)行通過):
            /*圈算法*/
            #include"stdio.h"
            int min(int x,int y)
            {if(x<y) return(x);
            else return(y);
            }
            void main()
            {int 
            a=0,b=0,i,j,k,p,n,t,A[10][10],P[10][10],B[10][10],C[10][10],D[10][10];
            printf("please input n:\n");
            scanf("%d",&n);
            printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            scanf("%7d,%7d",&C[i][j],&B[i][j]); 
//輸入各點(diǎn)(i,j)之間的容量C[i][j]和運(yùn)費(fèi)B[i][j]
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            {A[i][j]=C[i][j];D[i][j]=0;P[i][j]=B[i][j];}
            for(i=n;i>1;i--)
            for(j=i-1;j>0;j--)
            for(k=j-1;k>=0;k--)
            if(A[j][i]!=0&&A[k][j]!=0)
            D[k][j]=min(A[j][i],A[k][j]);
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            }
            for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
            for(k=j+1;k<=n;k++)
            if(D[i][j]!=0&&D[j][k]!=0)
            if(D[i][j]+D[j][k]==C[i][j])
            {A[i][j]=0;A[j][k]=0;A[j-i][k-j]=0;
            P[i][j]=100;P[j][k]=100;P[j-i][k-j]=0;
            a=a+C[i][j];
            b=b+B[i][j]*C[i][j]+B[j][k]*C[j][k]+B[j-i][k-j]*C[j-i][k-j];
            for(p=k+1;p<=n;p++)
            if(C[i][j]<C[k][p])
            {b=b+B[k][p]*C[i][j];
            A[k][p]=C[k][p]-C[i][j];
            }
            for(p=k-j+1;p<=n;p++)
            if(C[j-i][k-j]<C[k-j][p])
            {b=b+B[k-j][p]*C[j-i][k-j]+B[4][3]*C[4][3];
            A[k-j][p]=C[k-j][p]-C[j-i][k-j];
            }
            A[4][3]=0;
            }
            printf("a=%d,b=%d\n",a,b);
            for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            D[i][j]=0;
            for(i=n;i>1;i--)
            for(j=i-1;j>0;j--)
            for(k=j-1;k>=0;k--)
            if(A[j][i]!=0&&A[k][j]!=0)
            D[k][j]=min(A[j][i],A[k][j]);
            printf("D[%d][%d]:\n",n,n);
            for(i=0;i<=n;i++)
            {for(j=0;j<=n;j++)
            printf("%7d",D[i][j]);
            printf("\n");
            }
            for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
            for(k=j+1;k<=n;k++)
            if(D[i][j]!=0&&D[j][k]!=0)
            if(D[i][j]==D[j][k])
            for(p=k+1;p<=n;p++)
            {t=min(min(A[i][j],A[j][k]),min(A[j][k],A[k][p]));
            a=a+t;
            b=b+t*(B[i][j]+B[j][k]+B[k][p]);
            }
            printf("a=%d,b=%d\n",a,b);
            }

            運(yùn)行結(jié)果:
            please input n:
            5
            please input C[5][5],B[5][5]:
            0,0 4,1 5,3 0,100 0,100 0,100
            0,100 0,0 1,1 3,3 0,100 0,100
            0,100 0,100 0,0 0,100 2,4 0,100
            0,100 0,100 0,100 0,0 0,100 5,2
            0,100 0,100 0,100 1,1 0,0 2,4
            0,100 0,100 0,100 0,100 0,100 0,0
            D[5][5]:
            0 1 2 0 0 0
            0 0 1 3 0 0
            0 0 0 0 2 0
            0 0 0 0 0 0
            0 0 0 0 0 0
            0 0 0 0 0 0
            a=4,b=27
            D[5][5]:
            0 0 1 0 0 0
            0 0 0 0 0 0
            0 0 0 0 1 0
            0 0 0 0 0 0
            0 0 0 0 0 0
            0 0 0 0 0 0
            a=5,b=38
            //注：100表示Vi到Vj之間無可行路

            作者：云嫣『北峰數(shù)模』  http://mcm.zjnu.net.cn