830. The Best Average Loop

A courier network has n junctions numbered 1 .. n and m one-way roads. Road j runs from u[j] to v[j] and pays w[j], a whole number of rupees, never negative. Repeated roads and self-loops are allowed.

A LOOP is a directed cycle: a route that leaves a junction and comes back to it. Its average pay is its total pay divided by the number of roads it uses.

Print the largest whole number L such that some loop has average pay at least L. If the network has no loop at all, print -1.

roads 1->2 (4), 2->3 (6), 3->1 (8) -> 6 one loop, average 18/3 roads 1->2 (5), 2->1 (8) -> 6 13/2 is 6.5, so 6 roads 1->2 (5), 2->3 (5) -> -1 no loop

## Turning "is there a good loop?" into "is there a negative cycle?"

Fix a candidate L. Some loop has average pay at least L exactly when some loop C satisfies

sum over roads of w >= L * (number of roads)

which is the same as sum of (w - L) >= 0, and the same again as sum of (L - w) <= 0.

So reweight every road as L - w and ask whether the network has a cycle whose total is at most zero. That is nearly the classic negative-cycle question that Bellman-Ford answers, and the word "nearly" is the entire difficulty: Bellman-Ford detects cycles whose total is STRICTLY negative, and a cycle of total exactly zero is precisely the boundary case that decides the answer.

## The scaling trick

Reweight as

z = (L - w) * n - 1

instead. For a cycle of t roads, with t at most n, the total becomes n * sum(L - w) - t. Because sum(L - w) is an integer, only two cases exist:

sum(L - w) <= 0 then the z-total is at most -t, which is strictly negative sum(L - w) >= 1 then the z-total is at least n - t, which is at least 0

So the network has a cycle with sum(L - w) <= 0 if and only if it has a strictly negative cycle under z. The - 1 is a nudge small enough that n of them cannot cancel a full unit, which is exactly why the multiplier is n.

## Detecting the negative cycle

Set every distance to 0, which is the same as attaching a free source to every junction, and relax all m roads n times. If the nth pass still improves some distance, a negative cycle exists. If a pass changes nothing, stop early and report that none does.

## Why the predicate is monotone

Raising L cannot help any loop: for a fixed loop, sum(w) - L * t strictly decreases as L grows. So once no loop reaches L, none reaches anything larger, and the workable values of L form a PREFIX. The answer is the largest of them, so the loop searches for the last true:

mid = hi - (hi - lo) / 2 feasible(mid) ? lo = mid : hi = mid - 1

## The bounds, and the empty case

lo = 0. Pay is never negative, so any loop at all has average at least 0.

hi = max(w). No loop can average more than its best road.

Test L = 0 before the search. Under L = 0 every loop has sum(w - 0) >= 0, so the test succeeds exactly when the network contains SOME loop. If it fails, print -1 and stop. That is the whole detection of an acyclic network, reusing the same routine rather than a separate topological sort.

## Why the loop terminates

The upward midpoint gives lo < mid <= hi while lo < hi, so one branch raises lo and the other lowers hi, each strictly. About 20 iterations for pay up to 10^6.

## Overflow

(L - w) * n reaches 10^6 * 100 = 10^8, and a distance accumulated over n passes reaches 10^10. That is past 32 bits and comfortable in 64.

## Related problems

Problem 1645 finds the route whose WORST edge is smallest, by binary searching a threshold and testing reachability. This does the same thing one level up: the threshold is now an average rather than a single edge, and the test is a negative-cycle detection rather than a reachability sweep.

## Cost

Time O(n m log(max w)). Space O(n + m).

Constraints - `1 ≤ n ≤ 100` - `1 ≤ m ≤ 1000` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000` - Repeated roads and self-loops are allowed.