c++2959 问题 L: 卡车运输

Question

余博士教编程_酷哥OJ_酷哥爱编程_酷哥创客AI编程 https://oj.coolguymaker.com/problem.php?tag=contest&cid=5353&pid=11

注意：时间限制: 1.0 Sec 内存限制: 128 MB(n≤10000，m≤10000，vi≤100000)

Answer 1

引自免费微信小程序：皆我百晓生

题目描述： 在城市中有n个仓库，编号为1到n，每个仓库都有一定数量的货物，表示为数组v。同时，有m条道路连接这些仓库，每条道路由两个整数u, v表示从仓库u到仓库v有一条双向道路。你需要将所有仓库中的货物运送到一个指定的目标仓库t。每次可以使用一辆卡车运输，卡车可以从任意一个仓库出发，并且只能沿道路行驶，最终到达目标仓库t。每辆卡车的最大载货量是相同的，表示为整数W。

你的任务是计算至少需要多少辆卡车才能完成所有的货物运输。

解题思路： 这是一个典型的网络流问题，可以通过求最小割（Minimum Cut）或者最大流（Maximum Flow）的方法解决。这里我们采用 Ford-Fulkerson 算法实现最大流，找到从各个仓库到目标仓库t的最大可能流量，然后将这个流量除以每辆车的最大载货量W，向上取整得到所需的最少卡车数量。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 1e9;
const int MAX_VERTICES = 10005;
vector<pair<int, int>> graph[MAX_VERTICES];
int flow[MAX_VERTICES][MAX_VERTICES];

void add_edge(int u, int v, int capacity) {
    graph[u].push_back({v, capacity});
    graph[v].push_back({u, 0}); // 双向边
}

bool bfs(int source, int sink) {
    vector<bool> visited(MAX_VERTICES, false);
    queue<int> q;
    q.push(source);
    visited[source] = true;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (auto &edge : graph[current]) {
            int next = edge.first;
            int residual_capacity = edge.second - flow[current][next];

            if (!visited[next] && residual_capacity > 0) {
                q.push(next);
                visited[next] = true;
                flow[current][next] += residual_capacity;
                flow[next][current] -= residual_capacity;
            }
        }
    }

    return visited[sink];
}

int dfs(int current, int sink, int remaining_capacity) {
    if (current == sink || remaining_capacity == 0)
        return remaining_capacity;

    int max_flow = 0;

    for (auto &edge : graph[current]) {
        int next = edge.first;
        int residual_capacity = edge.second - flow[current][next];

        if (residual_capacity > 0 && !flow[next][current]) { // 非饱和边
            int new_flow = dfs(next, sink, min(residual_capacity, remaining_capacity));
            if (new_flow > 0) {
                flow[current][next] += new_flow;
                flow[next][current] -= new_flow;
                max_flow += new_flow;
                remaining_capacity -= new_flow;
            }
        }
    }

    return max_flow;
}

int max_flow(int source, int sink) {
    int max_flow = 0;
    while (bfs(source, sink)) {
        max_flow += dfs(source, sink, INF);
    }
    return max_flow;
}

int main() {
    int n, m, t, W;
    cin >> n >> m >> t >> W; // 输入仓库数量、道路数量、目标仓库编号和每辆车的最大载货量

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入道路的起点和终点
        add_edge(u, v, INF); // 添加道路并设置无限容量
    }

    // 初始化每辆卡车能装载的货物总量
    int total_load = 0;
    for (int i = 1; i <= n; i++) {
        int vi;
        cin >> vi; // 输入仓库i的货物量
        total_load += vi;
    }

    // 设置源节点为1，所有仓库作为中间节点，目标节点为t+1
    for (int i = 1; i <= n; i++) {
        add_edge(0, i, vi); // 从源节点到每个仓库
    }
    add_edge(n + 1, t + 1, INF); // 从目标仓库t到目标节点t+1

    int max_capacity = max_flow(0, t + 1); // 计算最大流
    int trucks_needed = ceil((double)total_load / max_capacity); // 计算最少卡车数量

    cout << trucks_needed << endl;

    return 0;
}

这段代码首先读入输入数据，然后构建图结构，接着调用Ford-Fulkerson算法计算最大流，最后根据总货物量和最大流计算出最少需要的卡车数量。注意，在计算最少卡车数量时，我们需要使用ceil()函数向上取整，因为卡车的数量必须是整数。