题解 | 物流网络最优运输路径

#include <climits>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;


struct Edge {
    int v;
    int w;
};


// 传入邻接表
void MainFunction(vector<vector<Edge>>& map) {
    int vNum = map.size();

    // 构造DAG判环
    vector<int> indeg(vNum);   // 入度列表
    for (vector<Edge>& es : map) {
        for (Edge& e : es) {
            indeg[e.v]++;
        }
    }

    vector<int> DAGser;  // DAG序列
    queue<int> q;
    for (int i = 0; i < vNum; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int u = q.front();
        DAGser.push_back(u);
        q.pop();
        for (Edge& e : map[u]) {
            if (--indeg[e.v] == 0) q.push(e.v);
        }
    }

    // 判环
    if (DAGser.size() != vNum) {
        cout << "-1";
        return ;
    }

    // 动态规划
    vector<int> dpW(vNum);
    vector<int> dpL(vNum);

    // 设置初值
    for (int i = 0; i < vNum; i++) {
        if (indeg[i] == 0) {
            dpW[i] = 0;
            dpL[i] = 1;
            continue;
        }
        dpW[i] = -(INT_MAX / 2);
        dpL[i] = 0;
    }

    // 状态转移
    for (int x : DAGser) {
        vector<Edge> es = map[x];
        for (Edge e : es) {
            int candpW = dpW[x] + e.w;
            int candpL = dpL[x] + 1;
            if (candpW > dpW[e.v]) {
                dpW[e.v] = candpW;
                dpL[e.v] = candpL;
            }
            if (candpW == dpW[e.v] && candpL > dpL[e.v]) dpL[e.v] = candpL;
        }
    }

    // 输出
    int maxIndex = 0;
    for (int i = 0; i < vNum; i++) {
        if (dpW[i] > dpW[maxIndex]) maxIndex = i;
    }

    if (dpW[maxIndex] == 0) {
        cout << 0 << " " << 0;
        return ;
    }
    cout << dpW[maxIndex] << " " << dpL[maxIndex];
    return ;

}


int main() {
    int es;
    cin >> es;

    vector<vector<Edge>> maxMap(1000);
    for (int i = 0; i < es ; ++i) {
        int v;
        cin >> v;
        Edge e;
        cin >> e.v;
        cin >> e.w;
        maxMap[v].push_back(e);
    }

    MainFunction(maxMap);

    return 0;
}