「网络流 24 题」运输问题 最大/小费用最大流

Posted on | In , ,

最大/小费用最大流裸题

题目链接

题解

  • 最大/小费用最大流裸题

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 405;
const int INF=1e9+7;




struct Edge
{
    int from, to, cap, flow, cost;
    Edge(int u,int v,int c,int f, int w):from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct MCMF
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    int d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<=n+1; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap,int cost)
    {
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int& flow, long long& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
          //  cout<<123<<endl;
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edges[G[u][i]];
                if( e.cap > e.flow && d[e.to] > d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t] == 1000000000+2)
            return false;
        flow += a[t];
        cost += (long long)d[t] * (long long)a[t];
        for(int u=t; u!=s; u=edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,long long& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
        return flow;
    }
};

int m, n, c[105][105], mc[105], ns[105];

int main()
{
    MCMF now;
    int st=0, ed=maxn-2;
    now.init(ed);
    scanf("%d%d", &m, &n);
    for(int i=1;i<=m;i++)
        scanf("%d", &mc[i]);
    for(int i=1;i<=n;i++)
        scanf("%d", &ns[i]);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d", &c[i][j]);
        }
    }

    for(int i=1;i<=m;i++)
    {

        now.Addedge(st, i, mc[i], 0);
        for(int j=1;j<=n;j++)
        {
            now.Addedge(i, j+m, INF,c[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        now.Addedge(i+m, ed, ns[i], 0);
    }
    ll ans1;
    now.MincostMaxflow(st, ed, ans1);
    now.init(ed);
    for(int i=1;i<=m;i++)
    {
        now.Addedge(st, i, mc[i], 0);
        for(int j=1;j<=n;j++)
        {
            now.Addedge(i, j+m, INF,-c[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        now.Addedge(i+m, ed, ns[i], 0);
    }
    ll ans2;
    now.MincostMaxflow(st, ed, ans2);
    printf("%lld\n%lld\n", ans1, -ans2);
}