Skip to content

FFLOW

Why Practice This

This is a useful flow problem because the statement looks like an undirected weighted graph problem, but the clean solution is still a standard s-t max-flow model with careful edge construction.

Recognition Cue

This is a straightforward throughput on a sparse capacitated network signal:

  • the statement asks for a maximum amount that can move from 1 to N
  • every edge has a capacity
  • the graph is undirected in the statement, but direction is not the hard part
  • the right question is global flow feasibility, not path-by-path greedy routing

If the problem asks for the largest transferable quantity through capacity-constrained connections, model first and only then choose the flow engine.

Problem-Specific Transformation

The statement is rewritten into a standard s-t flow network:

  • source s = 1
  • sink t = N
  • each undirected edge (u, v, c) becomes capacity c in both directions

After that, nothing problem-specific remains except judge-friendly implementation choices such as flat arrays and capacity scaling. The whole task becomes "run max flow on the correctly modeled network."

Core Idea

Treat the graph as a flow network with:

  • source s = 1
  • sink t = N
  • each undirected edge (u, v, c) represented by capacity c in both directions

Then the task is exactly the maximum flow problem.

Because the graph is sparse enough for a standard flow algorithm and the capacities are large, a good fit is Dinic's algorithm with long long capacities.

For vn.spoj, the implementation uses a more performance-oriented version:

  • flat edge arrays
  • manual BFS queue
  • capacity scaling

Complexity

  • Dinic is fast enough for the judge limits here
  • capacities use long long

Pitfalls / Judge Notes

For one undirected edge with capacity c between u and v, we add:

  • a directed edge u -> v with capacity c
  • a directed edge v -> u with capacity c

In the residual graph implementation, each of those directed edges also gets its own reverse edge of capacity 0.

Self-loops can be ignored because they never help send flow from 1 to N, and they never affect an s-t cut.

  • N <= 5000, M <= 30000
  • capacities can be up to 1e9
  • the answer may exceed 32-bit, so the implementation uses long long
  • duplicate edges are allowed and can be added directly
  • the solution uses a capacity-scaling version of Dinic's algorithm

Reusable Pattern

  • Topic page: Maximum Flow
  • Practice ladder: Maximum Flow ladder
  • Starter template: dinic.cpp
  • Notebook refresher: Graph cheatsheet
  • Carry forward: separate the reusable residual-network engine from the problem-specific source/sink modeling.
  • This note adds: the capacity-scaling and undirected-edge handling needed by this judge task.

Solutions