最小费用最大流 最小费用路 算法

#include <iostream>
#include <queue>
#define msize 1024
#define inf 1<<20
using namespace std;
 
int n,m,s,t;        //n个顶点，m条边，源点s，汇点t
int graph[msize][msize],flow[msize][msize],cost[msize][msize];
int pre[msize],dis[msize];
 
int deltaCost()      //从s到t的最小费用
{
    int res=0,i,j;
    bool quit;
 
    while (1)
    {
        //Bellman Ford
        for (int k=0;k<n;k++) dis[k]=inf;
        dis[s]=0;
        quit=false;
        pre[s]=s;
        while (!quit)
        {
            quit=true;
            for (i=0;i<n;i++)
                for (j=0;j<n;j++)
                    if (flow[i][j]<graph[i][j]&&dis[i]+cost[i][j]<dis[j])
                    {
                        dis[j]=dis[i]+cost[i][j];
                        pre[j]=i;
                        quit=false;
                    }
        }
        if (dis[t]==inf) break;
        int delta=inf;
        for (i=t;i!=s;i=pre[i])
            delta=min(delta,graph[pre[i]][i]-flow[pre[i]][i]);
 
        for (i=t;i!=s;i=pre[i])
        {
            flow[pre[i]][i] += delta;
            flow[i][pre[i]] = -flow[pre[i]][i];
        }
        res += delta*dis[t];
    }
 
    return res;
}
 
int main()
{
    char str[32];
    int id;
    int total_case;
    int a,b,c,d;
 
    scanf("%d",&total_case);
    while (total_case--)
    {
        scanf("%s%d",str,&id);
        scanf("%d%d%d%d",&n,&m,&s,&t);
        memset(flow,0,sizeof(flow));
        memset(cost,0,sizeof(cost));
        memset(graph,0,sizeof(graph));
        for (int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&a,&b,&d,&c);
            graph[a][b]=d;
            cost[a][b]=c;
            cost[b][a]=-c;
        }
        printf("%d\n",deltaCost());
    }
 
    return 0;
}