Chương trình C++ tìm lợi nhuận tối đa từ bán lúa mì giữa các thành phố

Mô tả bài toán

Có n thành phố kết nối bởi m đường đơn hướng. Giá lúa mì tại mỗi thành phố cho trước. Một thương nhân có thể mua lúa ở một thành phố, di chuyển theo các đường cho phép và bán ở thành phố khác. Tìm lợi nhuận lớn nhất có thể đạt được (giá bán - giá mua).

Ví dụ

n = 5, m = 3, giá = {4, 6, 7, 8, 5}, đường = {{1,2},{2,3},{2,4},{4,5}}. Đầu ra: 4 (mua ở thành phố 1 giá 4, bán ở thành phố 4 giá 8).

Thuật toán

1. Xây dựng đồ thị hướng từ mảng roads.
2. Khởi tạo mảng tp lưu giá mua nhỏ nhất có thể đạt đến mỗi đỉnh (khởi tạo = +∞).
3. Duyệt các đỉnh theo thứ tự topo (ở đây dùng chỉ số 0..n-1 vì đường chỉ đi từ chỉ số nhỏ đến lớn sau khi trừ 1). Với mỗi đỉnh u, cập nhật tp[v] = min(tp[v], tp[u], price[u]) cho mọi cạnh u→v.
4. Kết quả là max của price[i] - tp[i] trên tất cả đỉnh.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, vector<int> price, vector<pair<int,int>> roads) {
    vector<vector<int>> graph(n);
    for(int i = 0; i < m; i++) {
        int x = roads[i].first - 1;
        int y = roads[i].second - 1;
        graph[x].push_back(y);
    }
    const int INF = 1e9;
    vector<int> tp(n, INF);
    for(int i = 0; i < n; i++) {
        for(int u : graph[i]) {
            tp[u] = min({tp[u], tp[i], price[i]});
        }
    }
    int res = -INF;
    for(int i = 0; i < n; i++) {
        res = max(res, price[i] - tp[i]);
    }
    return res;
}

int main() {
    int n = 5, m = 3;
    vector<int> price = {4, 6, 7, 8, 5};
    vector<pair<int,int>> roads = {{1,2},{2,3},{2,4},{4,5}};
    cout << solve(n, m, price, roads);
    return 0;
}

Đầu vào / Đầu ra

Input: 5, 3, {4, 6, 7, 8, 5}, {{1, 2}, {2, 3}, {2, 4}, {4, 5}}

Output: 4