设有一个给定的网络N(V,x,y,A,C,w),其中c表示弧容量,w表示弧上的单位费用,另外给定一个常数a>o,请设计一个算法,用于求该网络中一个费用不超过a的最大流·要求给出算法的具体流程,并说明算法的合理性,进一步给出数值模拟的结果
急!
#include "stdio.h"
int 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]); //输入各点(i,j)之间的容量C[i][j]和运费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][k] + D[k][j];
for (p = 0; p <= n; p++)
P[i][j][p] = P[i][k][p] || P[k][j][p];
} //调用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中的数值确定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][k] + D[k][j];
for (p = 0; p <= n; p++)
P[i][j][p] = P[i][k][p] || P[k][j][p];
} //调用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中的数值确定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][k] + D[k][j];
for (p = 0; p <= n; p++)
P[i][j][p] = P[i][k][p] || P[k][j][p];
} //调用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中的数值确定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][k] + D[k][j];
for (p = 0; p <= n; p++)
P[i][j][p] = P[i][k][p] || P[k][j][p];
} //调用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的新最短路
}