Categories

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

用Bellman Ford找增广路进行增广
代码着实很烂,自己也还不太明白,先贴上来再说.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}

9 comments to 最小费用最大流 最小费用路 算法

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*