2646.最小化旅行的价格总和

链接：2646.最小化旅行的价格总和
难度：Hard
标签：树、深度优先搜索、图、数组、动态规划
简介：现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。给定路径的 价格总和 是该路径上所有节点的价格之和。另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。返回执行所有旅行的最小价格总和。

题解 1 - cpp

• 编辑时间：2023-04-16
• 执行用时：760ms
• 内存消耗：241.1MB
• 编程语言：cpp
• 解法介绍：树dp，记录选当前点和不选时的打折价格。

#define pii pair<int, int>
    #define X first
    #define Y second
    struct Node {
        int idx, price;
        vector<int> next;
    };
    struct QNode {
        int i, sum;
        vector<int> list;
    };
    class Solution {
    public:
        int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
            vector<Node> list(n);
            for (int i = 0; i < n; i++) {
                list[i].idx = i;
                list[i].price = price[i];
            }
            for (auto &edge : edges) {
                list[edge[0]].next.push_back(edge[1]);
                list[edge[1]].next.push_back(edge[0]);
            }
            // 记录所有路径
            vector<vector<QNode>> roads(n, vector<QNode>(n));
            for (int i = 0; i < n; i++) {
                roads[i][i] = QNode{ i, list[i].price, vector<int>(1, i)};
                queue<QNode> q;
                q.push(QNode{ i, list[i].price, vector<int>(1, i)});
                unordered_set<int> used;
                used.insert(i);
                while (q.size()) {
                    auto cur = q.front();
                    q.pop();
                    for (auto &next : list[cur.i].next) {
                        if (used.count(next)) continue;
                        used.insert(next);
                        auto nextNode = cur;
                        nextNode.i = next;
                        nextNode.sum += list[next].price;
                        nextNode.list.push_back(next);
                        roads[i][next] = nextNode;
                        q.push(nextNode);
                    }
                }
            }
            // 记录不打折时总价，和每个点会被遍历几次
            int sums = 0, res = 0x7fffffff;
            vector<int> weights(n, 0);
            for (auto &trip : trips) {
                sums += roads[trip[0]][trip[1]].sum;
                for (auto &item : roads[trip[0]][trip[1]].list) {
                    weights[item]++;
                }
            }
            // X 记录这个点选的时候最多能打多少
            // Y 记录这个点不选的时候最多能打多少
            unordered_set<int> used;
            function<pii(int)> discount = [&](int start) -> pii {
                pii res = make_pair(list[start].price / 2 * weights[start], 0);
                for (auto &next : list[start].next) {
                    if (used.count(next)) continue;
                    used.insert(next);
                    auto nextRes = discount(next);
                    res.X += nextRes.Y;                
                    res.Y += max(nextRes.X, nextRes.Y);
                    used.erase(next);
                }
                return res;
            };
            used.insert(0);
            auto disres = discount(0);
            res = min(res, sums - max(disres.X, disres.Y));
            used.erase(0);
            return res;
        }
    };

题解 2 - python

• 编辑时间：2023-12-06
• 执行用时：888ms
• 内存消耗：257.3MB
• 编程语言：python
• 解法介绍：提前统计每个点会被经过的次数，然后dp判断每个点打折和不打折的情况。

class Solution:
        def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
            nodes = [[] for _ in range(n)]
            for n1, n2 in edges:
                nodes[n1].append(n2)
                nodes[n2].append(n1)
            cnts = [0] * n
            def dfs(start: int, end: int, used: int) -> bool:
                if start == end:
                    cnts[end] += 1
                    return True
                check = False
                for next in nodes[start]:
                    if (used & (1 << next)) == 0 and dfs(next, end, used | (1 << next)):
                        cnts[start] += 1
                        check = True
                return check
            for start, end in trips: dfs(start, end, 1 << start)
            sums = sum(c * price[i] for i, c in enumerate(cnts))
            @cache
            def try_trip(idx: int, used: int, can: bool) -> int:
                res1 = 0
                if can: 
                    res1 += int(cnts[idx] * price[idx] / 2)
                    for next in nodes[idx]:
                        if (used & (1 << next)) == 0:
                            res1 += try_trip(next, used | (1 << next), not can)
                res2 = 0
                for next in nodes[idx]:
                    if (used & (1 << next)) == 0:
                        res2 += try_trip(next, used | (1 << next), True)
                return max(res1, res2)
            return min(sums - try_trip(i, 1 << i, True) for i in range(n))