3530. 有向无环图中合法拓扑排序的最大利润

3530. 有向无环图中合法拓扑排序的最大利润

给你一个由 n 个节点组成的有向无环图（DAG），节点编号从 0 到 n - 1，通过二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示一条从节点 ui 指向节点 vi 的有向边。每个节点都有一个对应的 得分 ，由数组 score 给出，其中 score[i] 表示节点 i 的得分。

你需要以 有效的拓扑排序 顺序处理这些节点。每个节点在处理顺序中被分配一个编号从 1 开始的位置。

将每个节点的得分乘以其在拓扑排序中的位置，然后求和，得到的值称为 利润。

请返回在所有合法拓扑排序中可获得的 最大利润 。

拓扑排序 是一个对 DAG 中所有节点的线性排序，使得每条有向边 u → v 中，节点 u 都出现在 v 之前。

示例 1：

输入： n = 2, edges = [[0,1]], score = [2,3]

输出： 8

解释：

节点 1 依赖于节点 0，因此一个合法顺序是 [0, 1]。

节点 处理顺序 得分 乘数 利润计算
0 第 1 个 2 1 2 × 1 = 2
1 第 2 个 3 2 3 × 2 = 6
所有合法拓扑排序中可获得的最大总利润是 2 + 6 = 8。

示例 2：

输入： n = 3, edges = [[0,1],[0,2]], score = [1,6,3]

输出： 25

解释：

节点 1 和 2 都依赖于节点 0，因此最优的合法顺序是 [0, 2, 1]。

节点 处理顺序 得分 乘数 利润计算
0 第 1 个 1 1 1 × 1 = 1
2 第 2 个 3 2 3 × 2 = 6
1 第 3 个 6 3 6 × 3 = 18
所有合法拓扑排序中可获得的最大总利润是 1 + 6 + 18 = 25。

提示：

1 <= n == score.length <= 22
1 <= score[i] <= 105
0 <= edges.length <= n * (n - 1) / 2
edges[i] == [ui, vi] 表示一条从 ui 到 vi 的有向边。
0 <= ui, vi < n
ui != vi
输入图 保证 是一个 DAG。
不存在重复的边。

解答：1. 全空，排序+累和。

2. tuopu(S)=在已有集合S的状态下，剩余的点获得的最大利润。

S=U全集时，利润为0。

3. 下一个点的选取， j未被选择过S>>j&1==0，j的前缀都已经被选择过S|1<<j==S

class Solution { public: int maxProfit(int n, vector<vector<int>>& edges, vector<int>& score) { if(edges.empty()) { ranges::sort(score); int ans = 0; for (int i = 0; i < n; i++) { ans+=(i+1)*score[i]; } return ans; } vector<int> pre(n); for(auto& e: edges) { pre[e[1]] |= 1<<e[0]; } vector<int> tmp(1<<n); auto tuopu = [&](this auto&& tuopu, int s) -> int { if(s == 1<<n) { return 0; } int& res = tmp[s]; if (res) { return res; } int i = popcount((unsigned) s); for(int j=0;j<n;j++) { if(((s>>j)&1)==0 && ((s | pre[j]) == s)) { res = max(res, tuopu(s | 1<<j)+score[j]*(i+1)); } } return res; }; return tuopu(0); } };