网络流算法，最小费用最大流问题

img


设有一个给定的网络N(V,x,y,A,C,w)，其中c表示弧容量，w表示弧上的单位费用，另外给定一个常数a>o，请设计一个算法，用于求该网络中一个费用不超过a的最大流·要求给出算法的具体流程，并说明算法的合理性，进一步给出数值模拟的结果
急！

img


看一下是不是你要的，不懂的可以问。


#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的新最短路
}