3419. Minimize the Maximum Edge Weight of Graph Medium

1/**
2 * [3419] Minimize the Maximum Edge Weight of Graph
3 *
4 * You are given two integers, n and threshold, as well as a directed weighted graph of n nodes numbered from 0 to n - 1. The graph is represented by a 2D integer array edges, where edges[i] = [Ai, Bi, Wi] indicates that there is an edge going from node Ai to node Bi with weight Wi.
5 * You have to remove some edges from this graph (possibly none), so that it satisfies the following conditions:
6 * 
7 * 	Node 0 must be reachable from all other nodes.
8 * 	The maximum edge weight in the resulting graph is minimized.
9 * 	Each node has at most threshold outgoing edges.
10 * 
11 * Return the minimum possible value of the maximum edge weight after removing the necessary edges. If it is impossible for all conditions to be satisfied, return -1.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 5, edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2</span>
16 * Output: <span class="example-io">1</span>
17 * Explanation:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2024/12/09/s-1.png" style="width: 300px; height: 233px;" />
19 * Remove the edge 2 -> 0. The maximum weight among the remaining edges is 1.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">n = 5, edges = [[0,1,1],[0,2,2],[0,3,1],[0,4,1],[1,2,1],[1,4,1]], threshold = 1</span>
24 * Output: <span class="example-io">-1</span>
25 * Explanation: 
26 * It is impossible to reach node 0 from node 2.
27 * </div>
28 * <strong class="example">Example 3:
29 * <div class="example-block">
30 * Input: <span class="example-io">n = 5, edges = [[1,2,1],[1,3,3],[1,4,5],[2,3,2],[3,4,2],[4,0,1]], threshold = 1</span>
31 * Output: <span class="example-io">2</span>
32 * Explanation: 
33 * <img alt="" src="https://assets.leetcode.com/uploads/2024/12/09/s2-1.png" style="width: 300px; height: 267px;" />
34 * Remove the edges 1 -> 3 and 1 -> 4. The maximum weight among the remaining edges is 2.
35 * </div>
36 * <strong class="example">Example 4:
37 * <div class="example-block">
38 * Input: <span class="example-io">n = 5, edges = [[1,2,1],[1,3,3],[1,4,5],[2,3,2],[4,0,1]], threshold = 1</span>
39 * Output: <span class="example-io">-1</span>
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	2 <= n <= 10^5
45 * 	1 <= threshold <= n - 1
46 * 	1 <= edges.length <= min(10^5, n * (n - 1) / 2).
47 * 	edges[i].length == 3
48 * 	0 <= Ai, Bi < n
49 * 	Ai != Bi
50 * 	1 <= Wi <= 10^6
51 * 	There may be multiple edges between a pair of nodes, but they must have unique weights.
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph/
57// discuss: https://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn min_max_weight(n: i32, edges: Vec<Vec<i32>>, threshold: i32) -> i32 {
63        0
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_3419() {
75    }
76}
77