货物调度

GitHub跳转原题关系图 Canvas 关系图返回列表

把城市-日期拆成时间扩展网络，用最小费用最大流同时决定运输路线和跨日库存。

OJ: shumeng

题目 ID: CSP201412E

难度:提高+/省选-

标签:网络流最小费用最大流时间扩展网络

日期: 2026-07-31 16:21

形式化题目

每个城市每天会生产和消耗货物，货物当天可沿道路无限量运输；未消耗的货物必须在某个城市仓库存一晚，且受容量和费用限制。调度方案按每周循环，求一周运输费和库存费之和的最小值。

思路

先看小数据基准。它把每吨货物单独增广，在残量网络中用 SPFA 找当前最短路：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:43
 */
// brute.cpp：小数据基准，逐吨使用 SPFA 求最短增广路。
// 与 main.cpp 的最小费用最大流算法结论一致，只适合小数据验证。
#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;
const int INF_CAP = 1000000000;

// 一条网络流边：to 为终点，rev 为反向边在终点邻接表中的下标，cap 为剩余容量
struct Edge {
    int to;
    int rev;
    int cap;
    int cost;
};

vector<vector<Edge> > graph;

// 加一条容量 cap、单位费用 cost 的边，并同时加入反向边。
void add_edge(int u, int v, int cap, int cost) {
    Edge forward = {v, (int)graph[v].size(), cap, cost};
    Edge backward = {u, (int)graph[u].size(), 0, -cost};
    graph[u].push_back(forward);
    graph[v].push_back(backward);
}

// 节点编号：城市 city 在第 day 天对应的节点下标。
int node_id(int day, int city, int n) {
    return day * n + city;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int production[10][7] = {};
    int demand[10][7] = {};
    int capacity[10], hold_cost[10];
    for (int city = 0; city < n; city++) {
        for (int day = 0; day < 7; day++) {
            cin >> production[city][day];
        }
        for (int day = 0; day < 7; day++) {
            cin >> demand[city][day];
        }
        cin >> capacity[city] >> hold_cost[city];
    }

    struct Road {
        int u;
        int v;
        int cost;
    };
    vector<Road> roads(m);
    for (int i = 0; i < m; i++) {
        cin >> roads[i].u >> roads[i].v >> roads[i].cost;
        roads[i].u--;
        roads[i].v--;
    }

    // 建时间扩展网络：源点 S 提供产量，汇点 T 消耗需求，
    // 仓库边负责从当天流入下一天，道路边在同一天内双向运输。
    int source = 7 * n;
    int sink = source + 1;
    graph.assign(sink + 1, vector<Edge>());
    int total = 0;
    for (int city = 0; city < n; city++) {
        for (int day = 0; day < 7; day++) {
            int current = node_id(day, city, n);
            add_edge(source, current, production[city][day], 0);
            add_edge(current, sink, demand[city][day], 0);
            add_edge(current, node_id((day + 1) % 7, city, n), capacity[city], hold_cost[city]);
            total += demand[city][day];
        }
    }
    for (int day = 0; day < 7; day++) {
        for (int i = 0; i < m; i++) {
            add_edge(node_id(day, roads[i].u, n), node_id(day, roads[i].v, n), INF_CAP, roads[i].cost);
            add_edge(node_id(day, roads[i].v, n), node_id(day, roads[i].u, n), INF_CAP, roads[i].cost);
        }
    }

    // 每轮用 SPFA 在残量网络中找最短增广路，只增广 1 吨货物。
    long long answer = 0;
    int sent = 0;
    int nodes = sink + 1;
    while (sent < total) {
        vector<int> distance(nodes, INF);
        vector<int> in_queue(nodes, 0);
        vector<int> previous_node(nodes);
        vector<int> previous_edge(nodes);
        queue<int> q;
        distance[source] = 0;
        q.push(source);
        in_queue[source] = 1;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = 0;
            for (int i = 0; i < (int)graph[u].size(); i++) {
                Edge &e = graph[u][i];
                if (e.cap == 0 || distance[e.to] <= distance[u] + e.cost) {
                    continue;
                }
                distance[e.to] = distance[u] + e.cost;
                previous_node[e.to] = u;
                previous_edge[e.to] = i;
                if (!in_queue[e.to]) {
                    in_queue[e.to] = 1;
                    q.push(e.to);
                }
            }
        }

        // 沿记录的前驱边回退，更新残量并累加本次增广的费用。
        int add = 1;
        for (int v = sink; v != source; v = previous_node[v]) {
            Edge &e = graph[previous_node[v]][previous_edge[v]];
            e.cap -= add;
            graph[v][e.rev].cap += add;
            answer += e.cost;
        }
        sent += add;
    }

    cout << answer << '\n';
    return 0;
}

建立时间扩展网络

令 $x(d,i)$ 表示城市 $i$ 在第 $d$ 天。源点连向 $x(d,i)$ 的容量是生产量； $x(d,i)$ 连向汇点的容量是需求量。每条道路在每一天各建一条双向边，费用为道路费； $x(d,i)$ 连向下一天同城节点的边容量为仓库容量、费用为库存费。第 7 天的“下一天”是第 1 天。

在这张时间扩展网络中发送全周总需求量，恰好对应一周循环调度。正式程序采用最小费用最大流：每轮以势能修正残量边费用后用 Dijkstra 求最短增广路，并按路径瓶颈容量一次增广。

网络结构示意

这张图展示一个城市两条道路连接下的网络局部（S 源点、T 汇点）：

text

1
2
3
4
5
6
7
8
9S --产量--> x(1,1) --需求--> T
              |
              | 仓库边（容量 = 仓库容量，费用 = 库存费）
              v
           x(2,1) --需求--> T
              |
              | 仓库边
              v
           x(3,1) ...

x(1,1) 还与道路另一端城市 $j$ 的 x(1,j) 有双向容量无限、费用为道路费的边。仓库边只改变日期，道路边只改变城市，两类边组合出完整的调度方案。

代码

cpp

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
143
144
145
146
147
148
149
150
151
152
153
154
155/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 23:01
 */
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);
const int INF_CAP = 1000000000;

struct Edge {
    int to;
    int rev;
    int cap;
    int cost;
};

class MinCostFlow {
public:
    vector<vector<Edge> > graph;

    explicit MinCostFlow(int n) : graph(n) {}

    void add_edge(int from, int to, int cap, int cost) {
        Edge forward = {to, (int)graph[to].size(), cap, cost};
        Edge backward = {from, (int)graph[from].size(), 0, -cost};
        graph[from].push_back(forward);
        graph[to].push_back(backward);
    }

    long long solve(int source, int sink, int need) {
        int node_count = (int)graph.size();
        vector<long long> potential(node_count, 0);
        vector<long long> distance(node_count);
        vector<int> previous_node(node_count);
        vector<int> previous_edge(node_count);
        long long answer = 0;
        int flow = 0;

        while (flow < need) {
            fill(distance.begin(), distance.end(), INF);
            distance[source] = 0;
            priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                           greater<pair<long long, int> > > queue;
            queue.push(make_pair(0, source));

            while (!queue.empty()) {
                pair<long long, int> current = queue.top();
                queue.pop();
                long long current_distance = current.first;
                int u = current.second;
                if (current_distance != distance[u]) continue;

                for (int i = 0; i < (int)graph[u].size(); i++) {
                    Edge &edge = graph[u][i];
                    if (edge.cap == 0) continue;
                    long long next_distance = current_distance + edge.cost
                                              + potential[u] - potential[edge.to];
                    if (next_distance >= distance[edge.to]) continue;
                    distance[edge.to] = next_distance;
                    previous_node[edge.to] = u;
                    previous_edge[edge.to] = i;
                    queue.push(make_pair(next_distance, edge.to));
                }
            }

            if (distance[sink] == INF) break;
            for (int i = 0; i < node_count; i++) {
                if (distance[i] != INF) potential[i] += distance[i];
            }

            int add = need - flow;
            for (int v = sink; v != source; v = previous_node[v]) {
                add = min(add, graph[previous_node[v]][previous_edge[v]].cap);
            }
            for (int v = sink; v != source; v = previous_node[v]) {
                Edge &edge = graph[previous_node[v]][previous_edge[v]];
                answer += (long long)add * edge.cost;
                edge.cap -= add;
                graph[v][edge.rev].cap += add;
            }
            flow += add;
        }
        return answer;
    }
};

int node_id(int day, int city, int n) {
    return day * n + city;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int production[100][7] = {};
    int demand[100][7] = {};
    int storage_capacity[100];
    int storage_cost[100];
    for (int city = 0; city < n; city++) {
        for (int day = 0; day < 7; day++) cin >> production[city][day];
        for (int day = 0; day < 7; day++) cin >> demand[city][day];
        cin >> storage_capacity[city] >> storage_cost[city];
    }

    struct Road {
        int u;
        int v;
        int cost;
    };
    vector<Road> roads(m);
    for (int i = 0; i < m; i++) {
        cin >> roads[i].u >> roads[i].v >> roads[i].cost;
        roads[i].u--;
        roads[i].v--;
    }

    int source = 7 * n;
    int sink = source + 1;
    MinCostFlow flow(sink + 1);
    int total_need = 0;
    for (int city = 0; city < n; city++) {
        for (int day = 0; day < 7; day++) {
            int current = node_id(day, city, n);
            if (production[city][day] > 0) {
                flow.add_edge(source, current, production[city][day], 0);
            }
            if (demand[city][day] > 0) {
                flow.add_edge(current, sink, demand[city][day], 0);
                total_need += demand[city][day];
            }

            int next_day = (day + 1) % 7;
            flow.add_edge(current, node_id(next_day, city, n),
                          storage_capacity[city], storage_cost[city]);
        }
    }

    for (int day = 0; day < 7; day++) {
        for (int i = 0; i < m; i++) {
            int u = node_id(day, roads[i].u, n);
            int v = node_id(day, roads[i].v, n);
            flow.add_edge(u, v, INF_CAP, roads[i].cost);
            flow.add_edge(v, u, INF_CAP, roads[i].cost);
        }
    }

    cout << flow.solve(source, sink, total_need) << '\n';
    return 0;
}

复杂度

设 $V=7n+2$ ， $E=O(7n+7m)$ ， $F$ 是全周总需求量。时间复杂度为 $O(FE\log V)$ ，空间复杂度为 $O(V+E)$ 。

总结

周期性物流的关键是把“日期”也放进状态。跨日库存边负责时间推进，第 7 天连回第 1 天保证调度可以无限重复；最小费用最大流则在所有运输和存储方案中选出总代价最小的一种。

图示解析

这张图串起时间扩展网络的四类边和求解目标：

text

1
2
3
4
5
6节点 x(d, i)：城市 i 的第 d 天
  |- S -> x(d, i)                   容量 = 生产量，费用 = 0
  |- x(d, i) -> T                   容量 = 需求量，费用 = 0
  |- x(d, i) -> x((d + 1) mod 7, i) 容量 = 仓库容量，费用 = 库存费
  `- x(d, i) <-> x(d, j)            容量 = 无限，费用 = 道路费
       `- 发送全周总需求量的最小费用流

同日道路边只改变城市，不改变日期；仓库边只改变日期，不改变城市。第 7 天连回第 1 天后，任何跨周库存都会被模型自然计入。

时间限制： 1.0 秒

空间限制： 256 MB

问题描述

某公司要处理一个周期性的物流问题。

有 $n$ 个城市，第 $i$ 个城市在每周的第 $j(1≤j≤7)$ 天会生产 $a_{i,j}$ 吨某种货物，同时需要消耗 $b_{i,j}$ 吨该种货物。已知每周的产量等于消耗量（即 $a_{i,j}$ 之和等于 $b_{i,j}$ 之和）。

城市之间有 $m$ 条道路，第 $k$ 条道路连接了城市 $s_k$ 和 $t_k$ 。一条道路上运输 $1$ 吨货物有一个固定的成本 $c_k$ 。道路都可以双向使用。每天运输的货物量没有限制。城市之间的距离并不远，货物可以从任意一个城市运输到任意另一个城市并且在当天到达。

货物如果在当天没有被消耗掉，就需要存放在仓库里过夜。第 $i$ 个城市的仓库容量为 $v_i$ ，存放 $1$ 吨货物过一夜所需的成本是 $w_i$ 。

请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话，该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。

输入格式

从标准输入读入数据。

输入的第一行有两个正整数 $n$ 和 $m$ ，即城市的个数和道路的条数。

接下来有 $n$ 行，每行包含 $16$ 个整数，用以描述第 $i$ 个城市的相关数据。其中第 $i$ 行包含的数为 $a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}, a_{i,5}, a_{i,6}, a_{i,7}, b_{i,1}, b_{i,2}, b_{i,3}, b_{i,4}, b_{i,5}, b_{i,6}, b_{i,7}, v_i, w_i$ 。

接下来有 $m$ 行，每行包含 $3$ 个整数，用以描述一条道路的相关数据。其中第 $k$ 行包含的数为 $s_k,t_k,c_k$ 。

输入数据中城市的编号均为 $1$ 到 $n$ 之间。输入数据的每行的行首行尾均保证没有空格，两个数之间恰好被一个空格隔开。

输出格式

输出到标准输出。

输出一行一个整数，即最优方案下每周的支出。

input1

1
2
3
4
5
6
73 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4
0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1
0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5
1 2 1
1 3 5
2 3 1

output1

样例 1 解释

城市 1 每周五生产 5 吨货物，把其中 2 吨运到存储费用低廉的城市 2 存储，把 1 吨运到城市 3 存储，剩下的 2 吨留在城市 1。

在次周一的时候城市 2 会消耗掉存放在那里的 2 吨货物。为了节约存储成本，将囤放在城市 1 的货物运到城市 2 存放。周三再将所有货物运到城市 3 以满足该城市的需求。

在此方案下，每周的运输成本为 8，每周的存储成本为 59，因此每周的总支出为 67。

子任务

对于 $100\%$ 的数据，保证：

$1≤n≤100,1≤m≤500,0≤a_{i,j},b_{i,j},v_i≤100,1≤w_i,c_k≤100$ ；
道路不存在重边和自环；
不会出现未消耗完货物且无法全部存入仓库的情况；
不会出现当天生产货物量加仓库库存量小于当天消耗货物量的情况。

货物调度

目录

形式化题目

思路

建立时间扩展网络

网络结构示意

代码

复杂度

总结

图示解析