最小费用流2.txt

常用C 语言 运筹学算法

/*网络算法*/
#include<stdio.h> 
long int min(int x,int y)     /*定义函数min （求x、y中的最小值）*/
{if(x<y) return(x);
 else return(y);}
void main()
{long 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 the capacity C[%d][%d] ,and the freight charge 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]);     /*输入各点(i,j)之间的容量C[i][j]和运费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]);       /*调用函数min*/
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]);         /*调用函数min*/
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[i][j]);       /*输出D数组*/
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);      /*输出最小费用b，最大流a*/
getch();   
}