Minimize the Maximum Edge Weight of Graph

This problem has a monotonic property: if we can find a valid subgraph with a maximum edge weight of W, we can certainly also find one for any maximum weight W' > W (since the set of allowed edges only grows). This property allows us to use binary search on the answer (the maximum allowed weight). We can efficiently search for the smallest possible value of max_w for which a valid subgraph exists.

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.

import java.util.*;

class Solution {
    public int minimizeMaxWeight(int n, int[][] edges, int threshold) {
        int low = 0, high = 1000001; // Weights are 1 to 10^6. Range [0, 10^6+1] is safe.
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(n, edges, mid)) {
                ans = mid;
                high = mid - 1; // Try for an even smaller max weight
            } else {
                low = mid + 1; // Need to allow larger weights
            }
        }
        return ans;
    }

    private boolean check(int n, int[][] edges, int maxWeight) {
        // Build the reversed graph with edges having weight <= maxWeight
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            if (edge[2] <= maxWeight) {
                // Add reversed edge: v -> u for original u -> v
                adj.get(edge[1]).add(edge[0]);
            }
        }

        // Run BFS from node 0 on the reversed graph to check reachability
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int count = 0;

        q.offer(0);
        visited[0] = true;
        count++;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                    count++;
                }
            }
        }

        // If all n nodes are visited, a valid subgraph exists
        return count == n;
    }
}