「网络流24题」负载平衡

Posted on | In , ,

G 公司有 $ n $ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $ n $ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

题目链接

建图分析

考虑图中的流量是所有仓库的盈余或者亏损量，建立二分图，左边集合为盈余的仓库，右边集合为亏损仓库，S和所有盈余的仓库建边容量为盈余量费用为0,T和所有亏损的建边容量为亏损量费用为0，每个点可以和同个集合相邻的两个点和不同集合的两个点建一条容量为INF费用为1的边，求最小费用最大流即可。

代码

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
#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;
    }

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

int n , sum, a[110];

int main()
{
    MCMF now;
    scanf("%d", &n);
    int st=0, ed=3*n+5;
    now.init(ed);
    for(int i=0;i<n;i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    sum /= n;
    for(int i=0;i<n;i++)
    {
        if(a[i]>sum)
        {
            now.Addedge(st, i+1, a[i]-sum, 0);

        }
        else if(a[i] <= sum)
        {
            now.Addedge(i+1+n, ed, sum-a[i], 0);
        }
    }
    for(int i=0;i<n;i++)
    {
        
            int l=(i-1+n)%n;
            int r=(i+1+n)%n;
            now.Addedge(i+1, l+1, INF, 1);
            now.Addedge(i+1, r+1, INF, 1);
            now.Addedge(i+1, l+1+n, INF, 1);
            now.Addedge(i+1,r+1+n,INF, 1);
        
    }
    ll ans;
    //cout<<1213<<endl;
    now.MincostMaxflow(st, ed, ans);
    printf("%lld\n", ans);
}