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

题目链接

物流网络最优运输路径

题目描述

一家物流公司规划了一个由多个城市和单向运输路线构成的商品运输网络。每条路线连接两个城市，并能产生一定利润。公司的目标是找到一条“最优运输链”。

定义与规则：

运输链：指从某个起点城市出发，沿着运输路线不重复地访问一系列城市的连续路径。
生产中心：所有运输链必须从“生产中心”开始。一个城市是“生产中心”，当且仅当它只发货而不收货，即在网络中没有任何路线指向它（入度为 0 的节点）。
最优标准：
- 主目标：找到能产生最大总利润的运输链。总利润是路径上所有路线利润的总和。
- 次目标：如果存在多条利润相同的运输链，选择其中经过城市数量最多的那一条（即路径最长的）。
无效网络：如果运输网络中存在循环路线，则整个网络设计不合理，无法规划。

输入描述：

第一行一个整数 $M$ ，表示运输路线总数。
接下来 $M$ 行，每行三个整数 $u, v, p$ ，表示一条从城市 $u$ 到城市 $v$ 的单向路线，利润为 $p$ 。

输出描述：

如果网络中存在环，输出 -1。
否则，输出两个用空格隔开的整数：最大总利润，以及在该利润下最长的运输链所经过的城市数量。

解题思路

本题可以分解为两个主要部分：首先，判断给定运输网络（有向图）是否存在环；其次，如果无环，则在该有向无环图（DAG）中寻找满足特定双重标准的最长路径。

第一步：建图与环路检测

图的表示：我们可以使用邻接表来表示这个有向图，其中每个节点存储其所有出边，每条边包含目标城市和利润。同时，需要一个数组 in_degree 来记录每个城市的入度。
环路检测：检测有向图中的环，最经典的方法是拓扑排序（基于 Kahn 算法）。
- 计算所有节点的入度。
- 将所有入度为 0 的节点（即“生产中心”）放入一个队列。
- 不断从队列中取出节点，并将其所有邻接节点的入度减 1。如果一个邻接节点的入度变为 0，则将其入队。
- 同时记录出队的节点数。如果最终出队的节点总数小于图中实际出现的节点总数，说明图中存在无法被拓扑排序访问到的节点，这些节点必然位于一个或多个环中。
- 如果检测到环，直接输出 -1 并结束。

第二步：动态规划求解最长路径

这是一个在 DAG 上求解最长路径的问题，可以使用动态规划配合记忆化搜索（DFS）来解决。

DP 状态定义：我们定义 dp[i] 为一个二元组 {max_profit, max_len}，表示从城市 i 出发所能获得的最优运输链的（最大利润，最长路径长度）。
状态转移：对于一个城市 u，其 dp[u] 的值可以通过其所有下游邻接城市 v 的 dp 值来计算。从 u 出发的最优路径，必然是走向某个邻居 v，然后加上从 v 出发的最优路径。 $dp[u] = max_{v \in neighbors(u)} { (profit(u,v) + dp[v].max_profit, 1 + dp[v].max_len) }$ 这里的 max 操作需要遵循题目的双重标准：优先比较利润，利润相同时再比较路径长度。
记忆化搜索 (DFS)：
- 编写一个 dfs(u) 函数来计算 dp[u]。
- 函数内部首先检查 dp[u] 是否已被计算过，如果是，则直接返回结果。
- 如果未计算，则初始化从 u 出发的基础路径为 {profit:0, len:1}（只包含城市 u 本身）。
- 遍历 u 的所有邻居 v，递归调用 dfs(v) 得到从 v 出发的最优解。
- 根据状态转移逻辑，结合 profit(u,v) 更新从 u 出发的最优解。
- 将计算结果存入 dp[u] 并返回。
求解最终答案：
- 在完成环路检测后，我们已经找到了所有的“生产中心”（入度为 0 的节点）。
- 遍历所有生产中心 s，对每一个调用 dfs(s) 计算从其出发的最优路径。
- 维护一个全局最优解 {global_max_profit, global_max_len}，用每个生产中心返回的结果来更新它，同样遵循题目的双重比较标准。
- 最终输出全局最优解。

注意：利润总和可能很大，需要使用长整型（long long 或 long）来存储。

代码

cpp
java
python

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

using namespace std;

using ll = long long;

map<int, vector<pair<int, int>>> adj;
map<int, pair<ll, int>> memo;

pair<ll, int> dfs(int u) {
    if (memo.count(u)) {
        return memo[u];
    }

    ll max_profit = 0;
    int max_len = 1;

    if (adj.count(u)) {
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int profit = edge.second;
            pair<ll, int> res = dfs(v);

            ll current_profit = profit + res.first;
            int current_len = 1 + res.second;

            if (current_profit > max_profit) {
                max_profit = current_profit;
                max_len = current_len;
            } else if (current_profit == max_profit) {
                if (current_len > max_len) {
                    max_len = current_len;
                }
            }
        }
    }
    return memo[u] = {max_profit, max_len};
}

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

    int m;
    cin >> m;

    map<int, int> in_degree;
    set<int> nodes;

    for (int i = 0; i < m; ++i) {
        int u, v, p;
        cin >> u >> v >> p;
        adj[u].push_back({v, p});
        in_degree[v]++;
        nodes.insert(u);
        nodes.insert(v);
    }
    
    // 确保所有节点都在 in_degree map 中
    for(int node : nodes) {
        if(in_degree.find(node) == in_degree.end()) {
            in_degree[node] = 0;
        }
    }

    // 环路检测
    queue<int> q;
    for (int node : nodes) {
        if (in_degree[node] == 0) {
            q.push(node);
        }
    }

    int count = 0;
    map<int, int> temp_in_degree = in_degree;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        count++;
        if (adj.count(u)) {
            for (auto& edge : adj[u]) {
                int v = edge.first;
                temp_in_degree[v]--;
                if (temp_in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }
    }

    if (count != nodes.size()) {
        cout << -1 << endl;
        return 0;
    }

    // DP
    ll final_max_profit = 0;
    int final_max_len = 0;

    for (int node : nodes) {
        if (in_degree[node] == 0) { // 是生产中心
            pair<ll, int> res = dfs(node);
            if (res.first > final_max_profit) {
                final_max_profit = res.first;
                final_max_len = res.second;
            } else if (res.first == final_max_profit) {
                if (res.second > final_max_len) {
                    final_max_len = res.second;
                }
            }
        }
    }

    cout << final_max_profit << " " << final_max_len << endl;

    return 0;
}

import java.util.*;

public class Main {
    
    // 邻接表，存储图的结构：u -> list of {v, profit}
    static Map<Integer, List<int[]>> adj = new HashMap<>();
    // 记忆化哈希表，存储从节点u出发的最优解 {maxProfit, maxLen}
    static Map<Integer, long[]> memo = new HashMap<>();

    // 深度优先搜索函数，计算从节点u出发的最优路径
    private static long[] dfs(int u) {
        if (memo.containsKey(u)) {
            return memo.get(u);
        }

        // 基础情况：路径只包含节点u本身，利润为0，长度为1
        long maxProfit = 0;
        long maxLen = 1;

        if (adj.containsKey(u)) {
            // 遍历所有下游邻居
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int profit = edge[1];
                // 递归计算从邻居v出发的最优解
                long[] res = dfs(v);
                
                long currentProfit = profit + res[0];
                long currentLen = 1 + res[1];

                // 根据双重标准更新最优解
                if (currentProfit > maxProfit) {
                    maxProfit = currentProfit;
                    maxLen = currentLen;
                } else if (currentProfit == maxProfit) {
                    if (currentLen > maxLen) {
                        maxLen = currentLen;
                    }
                }
            }
        }
        
        long[] result = new long[]{maxProfit, maxLen};
        memo.put(u, result);
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();

        Map<Integer, Integer> inDegree = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();
        
        // 建图并计算入度
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int p = sc.nextInt();
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, p});
            inDegree.put(v, inDegree.getOrDefault(v, 0) + 1);
            nodes.add(u);
            nodes.add(v);
        }
        
        for (int node : nodes) {
            inDegree.putIfAbsent(node, 0);
        }

        // 使用拓扑排序进行环路检测
        Queue<Integer> q = new LinkedList<>();
        for (int node : nodes) {
            if (inDegree.get(node) == 0) {
                q.offer(node);
            }
        }

        int count = 0;
        Map<Integer, Integer> tempInDegree = new HashMap<>(inDegree);
        while (!q.isEmpty()) {
            int u = q.poll();
            count++;
            if (adj.containsKey(u)) {
                for (int[] edge : adj.get(u)) {
                    int v = edge[0];
                    tempInDegree.put(v, tempInDegree.get(v) - 1);
                    if (tempInDegree.get(v) == 0) {
                        q.offer(v);
                    }
                }
            }
        }

        if (count != nodes.size()) {
            System.out.println(-1);
            return;
        }

        // 从所有生产中心（入度为0的节点）出发进行DP
        long finalMaxProfit = 0;
        long finalMaxLen = 0;
        
        for (int node : nodes) {
            if (inDegree.get(node) == 0) { // Is a production center
                long[] res = dfs(node);
                if (res[0] > finalMaxProfit) {
                    finalMaxProfit = res[0];
                    finalMaxLen = res[1];
                } else if (res[0] == finalMaxProfit) {
                    if (res[1] > finalMaxLen) {
                        finalMaxLen = res[1];
                    }
                }
            }
        }
        
        System.out.println(finalMaxProfit + " " + finalMaxLen);
    }
}

import sys

# 增加递归深度限制，以防深度过大的DAG
sys.setrecursionlimit(2000)

def solve():
    # 读取路线总数
    m = int(input())
    
    # 邻接表
    adj = {}
    # 记录每个节点的入度
    in_degree = {}
    # 记录所有出现过的节点
    nodes = set()

    # 建图并统计入度
    for _ in range(m):
        u, v, p = map(int, input().split())
        if u not in adj: adj[u] = []
        adj[u].append((v, p))
        
        in_degree[v] = in_degree.get(v, 0) + 1
        nodes.add(u)
        nodes.add(v)

    # 确保所有节点都在入度字典中
    for node in nodes:
        if node not in in_degree:
            in_degree[node] = 0
    
    # 使用拓扑排序进行环路检测
    q = [node for node in nodes if in_degree[node] == 0]
    count = 0
    temp_in_degree = dict(in_degree)
    
    head = 0
    while head < len(q):
        u = q[head]
        head += 1
        count += 1
        
        if u in adj:
            for v, p in adj[u]:
                temp_in_degree[v] -= 1
                if temp_in_degree[v] == 0:
                    q.append(v)

    if count != len(nodes):
        print(-1)
        return

    # 记忆化哈希表
    memo = {}

    def dfs(u):
        if u in memo:
            return memo[u]

        # 基础情况：路径只包含节点u，利润0，长度1
        max_profit, max_len = 0, 1
        if u in adj:
            for v, profit in adj[u]:
                # 递归计算下游节点的最优解
                res_profit, res_len = dfs(v)
                current_profit = profit + res_profit
                current_len = 1 + res_len
                
                # 根据双重标准更新
                if current_profit > max_profit:
                    max_profit = current_profit
                    max_len = current_len
                elif current_profit == max_profit:
                    if current_len > max_len:
                        max_len = current_len
        
        memo[u] = (max_profit, max_len)
        return max_profit, max_len

    final_max_profit, final_max_len = 0, 0
    # 从所有生产中心（入度为0）出发，寻找全局最优解
    for node in nodes:
        if in_degree[node] == 0:
            profit, length = dfs(node)
            if profit > final_max_profit:
                final_max_profit = profit
                final_max_len = length
            elif profit == final_max_profit:
                if length > final_max_len:
                    final_max_len = length
    
    print(final_max_profit, final_max_len)

solve()

算法及复杂度

算法：本题是一个在有向图上求解最长路径的经典问题，结合了环路检测。整体方案是：首先使用**拓扑排序（Kahn算法）来判断图是否为有向无环图（DAG），如果不是，则存在环路。如果是DAG，则在此基础上使用带记忆化搜索的动态规划（DP on DAG）**来寻找满足特定双重标准（最大利润优先，最长路径次之）的最优路径。
时间复杂度： $O(V+E)$ ，其中 $V$ 是城市（节点）数量， $E$ 是路线（边）数量。
- 建图与入度计算：遍历所有 $E$ 条路线，时间复杂度为 $O(E)$ 。
- 环路检测（拓扑排序）：需要访问每个节点和每条边一次，时间复杂度为 $O(V+E)$ 。
- 记忆化搜索：由于每个节点的 DP 状态只计算一次，dfs 函数对每个节点的总计算时间取决于其出度。所有 dfs 调用的总时间复杂度与访问所有节点和边的总次数成正比，即 $O(V+E)$ 。
- 因此，算法的瓶颈在于图的遍历，总体时间复杂度为 $O(V+E)$ 。
空间复杂度： $O(V+E)$ 。
- 邻接表：需要 $O(V+E)$ 的空间来存储图结构。
- 入度数组和节点集合：需要 $O(V)$ 的空间。
- 记忆化 DP 表：需要 $O(V)$ 的空间来存储每个节点的计算结果。
- 拓扑排序队列和递归栈：最多需要 $O(V)$ 的空间。
- 因此，总空间复杂度由图的存储决定，为 $O(V+E)$ 。