Skip to content

Police Chase

  • Title: Police Chase
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1695
  • Secondary topics: Minimum cut, Cut certificate, Undirected unit-capacity flow
  • Difficulty: medium
  • Subtype: Output any minimum set of streets whose removal disconnects node 1 from node n
  • Status: solved
  • Solution file: policechase.cpp

Why Practice This

This is one of the cleanest bridge problems between ordinary max-flow coding and the dual view behind optimization-and-duality.

You are not asked for the maximum amount of flow. You are asked for a certificate that blocks every route.

That is exactly where max-flow/min-cut becomes more than an algorithm:

  • flow gives the value
  • the residual graph reveals the cut
  • the cut is the object the statement actually wants

Recognition Cue

Reach for max-flow/min-cut duality when:

  • the statement asks for a minimum set of edges to remove
  • disconnecting source from sink is the actual goal
  • every removed edge has uniform or explicit capacity cost

The strongest smell is:

  • "remove the fewest streets so node 1 cannot reach node n"

That is the classic min-cut question hiding behind a flow computation.

Problem-Specific Transformation

The street-blocking story is rewritten as:

  • give every street unit capacity
  • compute the max flow
  • then extract a cut certificate from the residual graph

So the problem is not to invent the cut directly. It is:

  • solve the dual flow problem first
  • read the desired answer from residual reachability

Core Idea

Each undirected street can be closed at most once, so give every street capacity 1.

Model one undirected street (u, v) as:

  • directed edge u -> v with capacity 1
  • directed edge v -> u with capacity 1

Then compute the maximum flow from:

  • source s = 1
  • sink t = n

By the max-flow min-cut theorem, the maximum flow value equals the minimum number of streets that must be closed.

After the flow finishes:

  1. run DFS/BFS from s in the residual graph
  2. mark every reachable node
  3. every original street (u, v) with:
  4. u reachable and v unreachable, or
  5. v reachable and u unreachable belongs to one minimum cut

Those are exactly the streets we print.

Complexity

With n <= 500 and m <= 1000, standard Dinic is easily fast enough:

  • max flow: comfortably within limits
  • final residual DFS: O(n + m)

Pitfalls / Judge Notes

  • The streets are undirected, but the flow model still uses two directed unit-capacity edges.
  • Print streets from the original input graph, not residual edges.
  • The residual DFS must happen after max flow is complete.
  • Any minimum cut is accepted, so the order of printed streets does not matter.

Reusable Pattern

  • Topic page: Maximum Flow
  • Practice ladder: Maximum Flow ladder
  • Starter template: dinic.cpp
  • Notebook refresher: Graph cheatsheet
  • Carry forward: when the statement asks for edges to remove, think “compute max flow, then read the reachable side of the residual graph.”
  • This note adds: the explicit min-cut certificate extraction step that makes the dual view concrete.

Solutions