BGE - Homepage

3530. Maximum Profit from Valid Topological Order in DAG Hard

#Array #Dynamic Programming #Bit Manipulation #Graph Theory #Topological Sort #Bitmask
1/**
2 * [3530] Maximum Profit from Valid Topological Order in DAG
3 *
4 * You are given a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1, represented by a 2D array edges, where edges[i] = [ui, vi] indicates a directed edge from node ui to vi. Each node has an associated score given in an array score, where score[i] represents the score of node i.
5 * You must process the nodes in a valid topological order. Each node is assigned a 1-based position in the processing order.
6 * The profit is calculated by summing up the product of each node's score and its position in the ordering.
7 * Return the maximum possible profit achievable with an optimal topological order.
8 * A topological order of a DAG is a linear ordering of its nodes such that for every directed edge u &rarr; v, node u comes before v in the ordering.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 2, edges = [[0,1]], score = [2,3]</span>
13 * Output: <span class="example-io">8</span>
14 * Explanation:
15 * <img src="https://assets.leetcode.com/uploads/2025/03/10/screenshot-2025-03-11-at-021131.png" style="width: 200px; height: 89px;" />
16 * Node 1 depends on node 0, so a valid order is [0, 1].
17 * <table style="border: 1px solid black;">
18 * 	<thead>
19 * 		<tr>
20 * 			<th style="border: 1px solid black;">Node</th>
21 * 			<th style="border: 1px solid black;">Processing Order</th>
22 * 			<th style="border: 1px solid black;">Score</th>
23 * 			<th style="border: 1px solid black;">Multiplier</th>
24 * 			<th style="border: 1px solid black;">Profit Calculation</th>
25 * 		</tr>
26 * 	</thead>
27 * 	<tbody>
28 * 		<tr>
29 * 			<td style="border: 1px solid black;">0</td>
30 * 			<td style="border: 1px solid black;">1st</td>
31 * 			<td style="border: 1px solid black;">2</td>
32 * 			<td style="border: 1px solid black;">1</td>
33 * 			<td style="border: 1px solid black;">2 &times; 1 = 2</td>
34 * 		</tr>
35 * 		<tr>
36 * 			<td style="border: 1px solid black;">1</td>
37 * 			<td style="border: 1px solid black;">2nd</td>
38 * 			<td style="border: 1px solid black;">3</td>
39 * 			<td style="border: 1px solid black;">2</td>
40 * 			<td style="border: 1px solid black;">3 &times; 2 = 6</td>
41 * 		</tr>
42 * 	</tbody>
43 * </table>
44 * The maximum total profit achievable over all valid topological orders is 2 + 6 = 8.
45 * </div>
46 * <strong class="example">Example 2:
47 * <div class="example-block">
48 * Input: <span class="example-io">n = 3, edges = [[0,1],[0,2]], score = [1,6,3]</span>
49 * Output: <span class="example-io">25</span>
50 * Explanation:
51 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/10/screenshot-2025-03-11-at-023558.png" style="width: 200px; height: 124px;" />
52 * Nodes 1 and 2 depend on node 0, so the most optimal valid order is [0, 2, 1].
53 * <table data-end="1197" data-start="851" node="[object Object]" style="border: 1px solid black;">
54 * 	<thead data-end="920" data-start="851">
55 * 		<tr data-end="920" data-start="851">
56 * 			<th data-end="858" data-start="851" style="border: 1px solid black;">Node</th>
57 * 			<th data-end="877" data-start="858" style="border: 1px solid black;">Processing Order</th>
58 * 			<th data-end="885" data-start="877" style="border: 1px solid black;">Score</th>
59 * 			<th data-end="898" data-start="885" style="border: 1px solid black;">Multiplier</th>
60 * 			<th data-end="920" data-start="898" style="border: 1px solid black;">Profit Calculation</th>
61 * 		</tr>
62 * 	</thead>
63 * 	<tbody data-end="1197" data-start="991">
64 * 		<tr data-end="1059" data-start="991">
65 * 			<td style="border: 1px solid black;">0</td>
66 * 			<td style="border: 1px solid black;">1st</td>
67 * 			<td style="border: 1px solid black;">1</td>
68 * 			<td style="border: 1px solid black;">1</td>
69 * 			<td style="border: 1px solid black;">1 &times; 1 = 1</td>
70 * 		</tr>
71 * 		<tr data-end="1128" data-start="1060">
72 * 			<td style="border: 1px solid black;">2</td>
73 * 			<td style="border: 1px solid black;">2nd</td>
74 * 			<td style="border: 1px solid black;">3</td>
75 * 			<td style="border: 1px solid black;">2</td>
76 * 			<td style="border: 1px solid black;">3 &times; 2 = 6</td>
77 * 		</tr>
78 * 		<tr data-end="1197" data-start="1129">
79 * 			<td style="border: 1px solid black;">1</td>
80 * 			<td style="border: 1px solid black;">3rd</td>
81 * 			<td style="border: 1px solid black;">6</td>
82 * 			<td style="border: 1px solid black;">3</td>
83 * 			<td style="border: 1px solid black;">6 &times; 3 = 18</td>
84 * 		</tr>
85 * 	</tbody>
86 * </table>
87 * The maximum total profit achievable over all valid topological orders is 1 + 6 + 18 = 25.
88 * </div>
89 *  
90 * Constraints:
91 * 
92 * 	1 <= n == score.length <= 22
93 * 	1 <= score[i] <= 10^5
94 * 	0 <= edges.length <= n * (n - 1) / 2
95 * 	edges[i] == [ui, vi] denotes a directed edge from ui to vi.
96 * 	0 <= ui, vi < n
97 * 	ui != vi
98 * 	The input graph is guaranteed to be a DAG.
99 * 	There are no duplicate edges.
100 * 
101 */
102pub struct Solution {}
103
104// problem: https://leetcode.com/problems/maximum-profit-from-valid-topological-order-in-dag/
105// discuss: https://leetcode.com/problems/maximum-profit-from-valid-topological-order-in-dag/discuss/?currentPage=1&orderBy=most_votes&query=
106
107// submission codes start here
108
109impl Solution {
110    pub fn max_profit(n: i32, edges: Vec<Vec<i32>>, score: Vec<i32>) -> i32 {
111        0
112    }
113}
114
115// submission codes end
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn test_3530() {
123    }
124}
125
Back