Minimize the Maximum Edge Weight of Graph

1. Binary Search on the Answer: The problem asks to minimize a maximum value, which suggests binary search on the answer. The range of possible answers is from 1 to the maximum possible weight (10^6).
2. Define Search Range: Initialize low = 0, high = 10^6 + 1, and ans = -1.
3. Binary Search Loop: While low <= high: a. Calculate mid = low + (high - low) / 2 as the candidate for the maximum allowed weight. b. Call a helper function check(mid) to determine if it's possible to satisfy the conditions with mid as the maximum weight. c. If check(mid) returns true, it means mid is a possible answer. We store it and try for an even smaller maximum weight by setting high = mid - 1. d. If check(mid) returns false, mid is too small. We need to allow larger weights, so we set low = mid + 1.
4. Return Result: After the loop, ans will hold the minimum maximum weight found, or -1 if no solution is possible.
5. check(max_w) function: This function is identical to the one in the Linear Scan approach. It builds a reversed graph with edges of weight <= max_w and runs a traversal from node 0 to check if all n nodes are reachable.

The core of this approach is the binary search framework combined with the same check(max_w) function from the previous approach. The binary search dramatically reduces the number of times we need to call the check function.

Instead of checking every unique weight, we check the middle value mid of our current search range [low, high].

• If check(mid) is true, we know that a solution exists for max_w = mid. This means mid is a potential answer, and there might be an even better (smaller) one. So, we record mid as our current best answer and narrow our search to the lower half: high = mid - 1.
• If check(mid) is false, it's impossible to satisfy the conditions with the current max_w. We must allow edges with higher weights, so we narrow our search to the upper half: low = mid + 1.

This process continues until low > high, at which point we have found the minimum max_w that works.

The logic for the check(max_w) function remains the same: it verifies that if we only consider edges with weight at most max_w, it's possible for all nodes to reach node 0. As explained before, the threshold constraint is implicitly satisfied if reachability is met, because we can always construct a subgraph (a spanning arborescence) where each node's out-degree is at most 1.

1import java.util.*;2 3class Solution {4    public int minimizeMaxWeight(int n, int[][] edges, int threshold) {5        int low = 0, high = 1000001; // Weights are 1 to 10^6. Range [0, 10^6+1] is safe.6        int ans = -1;7 8        while (low <= high) {9            int mid = low + (high - low) / 2;10            if (check(n, edges, mid)) {11                ans = mid;12                high = mid - 1; // Try for an even smaller max weight13            } else {14                low = mid + 1; // Need to allow larger weights15            }16        }17        return ans;18    }19 20    private boolean check(int n, int[][] edges, int maxWeight) {21        // Build the reversed graph with edges having weight <= maxWeight22        List<List<Integer>> adj = new ArrayList<>();23        for (int i = 0; i < n; i++) {24            adj.add(new ArrayList<>());25        }26        for (int[] edge : edges) {27            if (edge[2] <= maxWeight) {28                // Add reversed edge: v -> u for original u -> v29                adj.get(edge[1]).add(edge[0]);30            }31        }32 33        // Run BFS from node 0 on the reversed graph to check reachability34        Queue<Integer> q = new LinkedList<>();35        boolean[] visited = new boolean[n];36        int count = 0;37 38        q.offer(0);39        visited[0] = true;40        count++;41 42        while (!q.isEmpty()) {43            int u = q.poll();44            for (int v : adj.get(u)) {45                if (!visited[v]) {46                    visited[v] = true;47                    q.offer(v);48                    count++;49                }50            }51        }52 53        // If all n nodes are visited, a valid subgraph exists54        return count == n;55    }56}

1. Identify Search Space: The possible values for the maximum edge weight range from the minimum weight present in the graph to the maximum. We can collect all unique weights and sort them to define an ordered search space.
2. Linear Scan: Iterate through each unique weight w from the sorted list, from smallest to largest.
3. Check Feasibility: For each w, treat it as the potential maximum allowed weight (max_w). We need to check if it's possible to satisfy the problem's conditions with this max_w.
4. Feasibility Check (check(max_w)): a. Construct a temporary graph containing only the edges from the input with weight less than or equal to max_w. b. The condition that node 0 must be reachable from all other nodes is equivalent to checking if all other nodes are reachable from node 0 in the reversed graph. c. Build the reversed graph. d. Perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from node 0 on the reversed graph. e. If the traversal visits all n nodes, it means a valid subgraph can be formed, and the function returns true.
5. Find First Valid Weight: The first w for which check(w) returns true is the minimum possible maximum weight. Return this w.
6. Handle Impossible Case: If the loop completes and no such w is found, it's impossible to satisfy the conditions. Return -1.

For a given candidate maximum weight max_w, we need a way to check if a valid subgraph exists. A subgraph is valid if:

1. All its edges have weights <= max_w.
2. All other nodes can reach node 0.
3. Every node's out-degree is at most threshold.

The crucial insight is that if reachability is possible (condition 2), we can always satisfy the out-degree constraint (condition 3). This is because if every node can reach node 0, we can form a spanning arborescence rooted at 0 on the graph of reachable nodes. In such an arborescence, every node except the root has an out-degree of exactly 1. Since the problem states threshold >= 1, this out-degree of 1 will always be less than or equal to threshold. Therefore, the check for a given max_w simplifies to just verifying reachability.

To check reachability, we can build a graph containing only edges with weight <= max_w, reverse all the edges, and then run a single BFS/DFS from node 0 to see if all nodes in the graph are visited. If they are, a valid subgraph exists.

This approach iterates through each unique weight and performs a full graph traversal, which can be slow if there are many unique weights.

1import java.util.*;2 3class Solution {4    public int minimizeMaxWeight(int n, int[][] edges, int threshold) {5        Set<Integer> weightSet = new HashSet<>();6        for (int[] edge : edges) {7            weightSet.add(edge[2]);8        }9        List<Integer> sortedWeights = new ArrayList<>(weightSet);10        Collections.sort(sortedWeights);11 12        for (int maxWeight : sortedWeights) {13            if (check(n, edges, maxWeight)) {14                return maxWeight;15            }16        }17 18        return -1;19    }20 21    private boolean check(int n, int[][] edges, int maxWeight) {22        List<List<Integer>> adj = new ArrayList<>();23        for (int i = 0; i < n; i++) {24            adj.add(new ArrayList<>());25        }26        for (int[] edge : edges) {27            if (edge[2] <= maxWeight) {28                // Reversed edge: v -> u for original u -> v29                adj.get(edge[1]).add(edge[0]);30            }31        }32 33        Queue<Integer> q = new LinkedList<>();34        boolean[] visited = new boolean[n];35        int count = 0;36 37        q.offer(0);38        visited[0] = true;39        count++;40 41        while (!q.isEmpty()) {42            int u = q.poll();43            for (int v : adj.get(u)) {44                if (!visited[v]) {45                    visited[v] = true;46                    q.offer(v);47                    count++;48                }49            }50        }51 52        return count == n;53    }54}