| Test | Method | Scope | |------|--------|-------| | Tiny random graphs | Exhaustive subset enumeration and Edmonds–Karp | every pair, 300 graphs, n = 2..9 | | Random sparse subgraphs | Independent Edmonds–Karp max-flow | every pair, 40 graphs, n = 20..79, caps up to 1e12 | | Edge cases | Edmonds–Karp | parallel edges, self-loops, disconnected, 1e12 caps, zero caps | | Scale test | Timing + spot checks vs Edmonds–Karp | n = 2000, m = 20000, caps up to 1e12 |
The solution is complete and verified end-to-end. Here is the deliverable (also saved to ~/solution.md):
A complete, verified Go implementation of:
int64 capacities.n-1 max-flow computations instead of n(n-1)/2).s-t cut for every pair equals the minimum edge weight on the unique tree path.Target: n ≤ 2000, m ≤ 20000, integer capacities up to 1e12.
With c ≤ 1e12, a single augmenting path can carry more than 2^30 ≈ 1.07e9. The classic const INF = 1 << 30 used as the initial DFS push bound or the initial "minimum on path" value silently caps every flow at ~1e9, so all cuts above that are wrong. Summing cut capacities over up to 20000 edges reaches 2e16, overflowing 32-bit int.
Fix: every capacity, flow accumulator, and sentinel is int64; the true sentinel is 1 << 62 ≈ 4.6e18, safely above the maximum possible cut m · maxc = 20000 · 1e12 = 2e16.
If an undirected edge {u,v} capacity c is added as a normal directed arc with reverse capacity 0, the residual is wrong: after sending f along u→v, the reverse residual must be c + f, not f. This overestimates min cuts.
Fix: add the two arcs as a mutually reverse pair, both initialised to c:
g[u] = append(g[u], arc{to: v, rev: len(g[v]), cap: c})
g[v] = append(g[v], arc{to: u, rev: len(g[u]) - 1, cap: c})
Now u→v holds c - f and v→u holds c + f, exactly the undirected residual.
After the min cut for (s,t) with t = parent[s], update only:
for i := s + 1; i < n; i++ {
if parent[i] == t && reach[i] { // reach = s-side of the cut
parent[i] = s
}
}
Common mistakes: iterating over all i != s (corrupts finalised nodes), using the t-side, or forgetting the parent[i] == t guard.
delta must start at the highest power of two ≤ max capacity, be applied in both BFS and DFS (cap >= delta), and each phase must run until no delta-augmenting path remains before halving. The loop for delta <= maxCap/2 { delta <<= 1 } avoids overflow.
The min-cut s-side is the set reachable from s in the final residual graph (cap > 0). Reading it before scaling finishes, or from t, breaks the cut tree.
Save as main.go, then:
go mod init gh
go run . test # correctness
go run . bench # performance
package main
import (
"fmt"
"math/rand"
"os"
"time"
)
// Capacity-scaling Dinic max-flow for undirected graphs with int64 capacities.
// An undirected edge {u,v} of capacity c is modelled as a pair of mutually
// reverse arcs, each initialised to c. This yields residual capacity c-f in
// the direction of flow and c+f in the opposite direction, exactly modelling
// the undirected capacity constraint |f| <= c.
type RawEdge struct {
u, v int
c int64
}
type arc struct {
to int
rev int
cap int64
}
type dinic struct {
g [][]arc
level []int
iter []int
delta int64
n int
}
func newDinic(n int, edges []RawEdge) *dinic {
d := &dinic{
g: make([][]arc, n),
level: make([]int, n),
iter: make([]int, n),
n: n,
}
for _, e := range edges {
if e.c <= 0 || e.u == e.v {
continue
}
// two mutually-reverse arcs, both with capacity c (undirected edge)
d.g[e.u] = append(d.g[e.u], arc{to: e.v, rev: len(d.g[e.v]), cap: e.c})
d.g[e.v] = append(d.g[e.v], arc{to: e.u, rev: len(d.g[e.u]) - 1, cap: e.c})
}
return d
}
func (d *dinic) bfs(s, t int) bool {
for i := range d.level {
d.level[i] = -1
}
d.level[s] = 0
q := make([]int, 0, d.n)
q = append(q, s)
for len(q) > 0 {
u := q[0]
q = q[1:]
for _, e := range d.g[u] {
if e.cap >= d.delta && d.level[e.to] < 0 {
d.level[e.to] = d.level[u] + 1
q = append(q, e.to)
}
}
}
return d.level[t] >= 0
}
func (d *dinic) dfs(u, t int, f int64) int64 {
if u == t {
return f
}
for ; d.iter[u] < len(d.g[u]); d.iter[u]++ {
e := &d.g[u][d.iter[u]]
if e.cap >= d.delta && d.level[e.to] == d.level[u]+1 {
pushed := d.dfs(e.to, t, min64(f, e.cap))
if pushed > 0 {
e.cap -= pushed
d.g[e.to][e.rev].cap += pushed
return pushed
}
}
}
return 0
}
// maxflow returns the value of a maximum s-t flow and the set of vertices
// reachable from s in the final residual graph (the s-side of a min cut).
func (d *dinic) maxflow(s, t int) (int64, []bool) {
if s == t {
return 0, nil
}
var maxCap int64
for _, adj := range d.g {
for _, e := range adj {
if e.cap > maxCap {
maxCap = e.cap
}
}
}
if maxCap == 0 {
reach := make([]bool, d.n)
reach[s] = true
return 0, reach
}
// highest power of two <= maxCap
d.delta = 1
for d.delta <= maxCap/2 {
d.delta <<= 1
}
var flow int64
for d.delta > 0 {
for d.bfs(s, t) {
for i := range d.iter {
d.iter[i] = 0
}
for {
pushed := d.dfs(s, t, int64(1)<<62)
if pushed == 0 {
break
}
flow += pushed
}
}
if d.delta == 1 {
break
}
d.delta >>= 1
}
reach := make([]bool, d.n)
stack := []int{s}
reach[s] = true
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, e := range d.g[u] {
if e.cap > 0 && !reach[e.to] {
reach[e.to] = true
stack = append(stack, e.to)
}
}
}
return flow, reach
}
func min64(a, b int64) int64 {
if a < b {
return a
}
return b
}
// GomoryHu builds a Gomory-Hu cut tree using Gusfield's simplification.
// parent[0] is unused (set to -1). For s>=1 the tree edge (s,parent[s]) has
// weight weight[s]. The min s-t cut for any pair equals the minimum weight on
// the unique tree path.
func GomoryHu(n int, edges []RawEdge) (parent []int, weight []int64) {
parent = make([]int, n)
weight = make([]int64, n)
parent[0] = -1
for i := 1; i < n; i++ {
parent[i] = 0
}
for s := 1; s < n; s++ {
t := parent[s]
d := newDinic(n, edges)
flow, reach := d.maxflow(s, t)
for i := s + 1; i < n; i++ {
if parent[i] == t && reach[i] {
parent[i] = s
}
}
weight[s] = flow
}
return parent, weight
}
// TreePathMin returns the minimum edge weight on the path u..v of the cut tree.
func TreePathMin(n int, parent []int, weight []int64, u, v int) int64 {
if u == v {
return 0
}
// build adjacency
type we struct {
to int
w int64
}
adj := make([][]we, n)
for s := 1; s < n; s++ {
p := parent[s]
adj[s] = append(adj[s], we{p, weight[s]})
adj[p] = append(adj[p], we{s, weight[s]})
}
// DFS from u to v
type node struct {
v int
par int
mn int64
}
stack := []node{{u, -1, int64(1) << 62}}
for len(stack) > 0 {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if cur.v == v {
return cur.mn
}
for _, e := range adj[cur.v] {
if e.to == cur.par {
continue
}
m := cur.mn
if e.w < m {
m = e.w
}
stack = append(stack, node{e.to, cur.v, m})
}
}
return -1
}
// ---- independent verification implementations ----
// BruteForceMinCut enumerates all vertex subsets containing s and not t.
// Feasible only for tiny n (n <= ~16). Returns the min cut value.
func BruteForceMinCut(n int, edges []RawEdge, s, t int) int64 {
best := int64(1) << 62
for mask := 0; mask < (1 << n); mask++ {
if mask&(1<<s) == 0 || mask&(1<<t) != 0 {
continue
}
var cut int64
for _, e := range edges {
inU := mask&(1<<e.u) != 0
inV := mask&(1<<e.v) != 0
if inU != inV {
cut += e.c
}
}
if cut < best {
best = cut
}
}
return best
}
// EdmondsKarpMinCut is an independent (BFS-augmenting) max-flow used to
// cross-check Dinic on arbitrary sizes. Directed residual representation of
// undirected edges: both arcs capacity c, reverse of each other.
type ekArc struct {
to, rev int
cap int64
}
func EdmondsKarpMinCut(n int, edges []RawEdge, s, t int) int64 {
if s == t {
return 0
}
g := make([][]ekArc, n)
for _, e := range edges {
if e.c <= 0 || e.u == e.v {
continue
}
g[e.u] = append(g[e.u], ekArc{e.v, len(g[e.v]), e.c})
g[e.v] = append(g[e.v], ekArc{e.u, len(g[e.u]) - 1, e.c})
}
var flow int64
for {
parV := make([]int, n)
parE := make([]int, n)
for i := range parV {
parV[i] = -1
}
parV[s] = s
q := []int{s}
for len(q) > 0 && parV[t] < 0 {
u := q[0]
q = q[1:]
for i, e := range g[u] {
if e.cap > 0 && parV[e.to] < 0 {
parV[e.to] = u
parE[e.to] = i
q = append(q, e.to)
}
}
}
if parV[t] < 0 {
break
}
// bottleneck
bott := int64(1) << 62
for v := t; v != s; v = parV[v] {
e := g[parV[v]][parE[v]]
if e.cap < bott {
bott = e.cap
}
}
for v := t; v != s; v = parV[v] {
u := parV[v]
e := &g[u][parE[v]]
e.cap -= bott
g[v][e.rev].cap += bott
}
flow += bott
}
return flow
}
// ---- test harness ----
func main() {
mode := "all"
if len(os.Args) > 1 {
mode = os.Args[1]
}
switch mode {
case "test":
runRandomTests()
case "bench":
runBench()
default:
runRandomTests()
runBench()
}
}
// runRandomTests cross-checks the Gomory-Hu tree for every vertex pair
// against (a) brute force on tiny graphs and (b) Edmonds-Karp on random
// sparse subgraphs.
func runRandomTests() {
fmt.Println("== randomized correctness tests ==")
rng := rand.New(rand.NewSource(12345))
for iter := 0; iter < 300; iter++ {
n := 2 + rng.Intn(8) // 2..9
// random sparse graph
var edges []RawEdge
seen := map[[2]int]bool{}
extra := rng.Intn(n + 2)
for k := 0; k < n-1+extra; k++ {
u := rng.Intn(n)
v := rng.Intn(n)
if u == v {
continue
}
if u > v {
u, v = v, u
}
key := [2]int{u, v}
if seen[key] {
continue
}
seen[key] = true
c := int64(1 + rng.Intn(20))
edges = append(edges, RawEdge{u, v, c})
}
if len(edges) == 0 {
continue
}
parent, weight := GomoryHu(n, edges)
for s := 0; s < n; s++ {
for t := s + 1; t < n; t++ {
got := TreePathMin(n, parent, weight, s, t)
bf := BruteForceMinCut(n, edges, s, t)
ek := EdmondsKarpMinCut(n, edges, s, t)
if got != bf || got != ek {
fmt.Printf("FAIL iter=%d n=%d s=%d t=%d gh=%d brute=%d ek=%d edges=%v\n",
iter, n, s, t, got, bf, ek, edges)
os.Exit(1)
}
}
}
}
fmt.Println(" tiny graphs vs brute force + Edmonds-Karp: OK")
// Larger sparse subgraphs vs Edmonds-Karp only.
for iter := 0; iter < 40; iter++ {
n := 20 + rng.Intn(60) // 20..79
m := n + rng.Intn(3*n)
var edges []RawEdge
seen := map[[2]int]bool{}
for len(edges) < m {
u := rng.Intn(n)
v := rng.Intn(n)
if u == v {
continue
}
if u > v {
u, v = v, u
}
key := [2]int{u, v}
if seen[key] {
continue
}
seen[key] = true
c := int64(1 + rng.Int63n(1_000_000_000_000))
edges = append(edges, RawEdge{u, v, c})
}
parent, weight := GomoryHu(n, edges)
for s := 0; s < n; s++ {
for t := s + 1; t < n; t++ {
got := TreePathMin(n, parent, weight, s, t)
ek := EdmondsKarpMinCut(n, edges, s, t)
if got != ek {
fmt.Printf("FAIL iter=%d n=%d s=%d t=%d gh=%d ek=%d\n", iter, n, s, t, got, ek)
os.Exit(1)
}
}
}
}
fmt.Println(" medium sparse graphs vs Edmonds-Karp: OK")
runEdgeCases()
}
// runEdgeCases exercises multi-edges, self-loops, disconnected graphs, and
// near-limit capacities, checking every pair against Edmonds-Karp.
func runEdgeCases() {
type tc struct {
name string
n int
edges []RawEdge
}
cases := []tc{
{"parallel edges", 3, []RawEdge{{0, 1, 5}, {0, 1, 7}, {1, 2, 4}, {0, 2, 100}}},
{"self loops", 3, []RawEdge{{0, 0, 999}, {0, 1, 3}, {1, 2, 3}, {0, 2, 3}}},
{"disconnected", 5, []RawEdge{{0, 1, 9}, {2, 3, 4}}},
{"path graph", 6, []RawEdge{{0, 1, 1e12}, {1, 2, 1e12}, {2, 3, 1e12}, {3, 4, 1e12}, {4, 5, 1e12}}},
{"max caps star", 5, []RawEdge{{0, 1, 1e12}, {0, 2, 1e12}, {0, 3, 1e12}, {0, 4, 1e12}}},
{"zero caps", 3, []RawEdge{{0, 1, 0}, {1, 2, 0}}},
}
for _, c := range cases {
parent, weight := GomoryHu(c.n, c.edges)
for s := 0; s < c.n; s++ {
for t := s + 1; t < c.n; t++ {
got := TreePathMin(c.n, parent, weight, s, t)
ek := EdmondsKarpMinCut(c.n, c.edges, s, t)
if got != ek {
fmt.Printf("FAIL edge case %q (%d,%d): gh=%d ek=%d\n", c.name, s, t, got, ek)
os.Exit(1)
}
}
}
}
fmt.Println(" edge cases (multi/self/disconnected/1e12/zero): OK")
}
func runBench() {
fmt.Println("== performance (n=2000, m=20000, caps up to 1e12) ==")
rng := rand.New(rand.NewSource(999))
n := 2000
m := 20000
edges := make([]RawEdge, 0, m)
seen := map[[2]int]bool{}
// ensure connectivity with a spanning tree
for i := 1; i < n; i++ {
p := rng.Intn(i)
edges = append(edges, RawEdge{p, i, int64(1 + rng.Int63n(1_000_000_000_000))})
seen[[2]int{p, i}] = true
}
for len(edges) < m {
u := rng.Intn(n)
v := rng.Intn(n)
if u == v {
continue
}
if u > v {
u, v = v, u
}
key := [2]int{u, v}
if seen[key] {
continue
}
seen[key] = true
edges = append(edges, RawEdge{u, v, int64(1 + rng.Int63n(1_000_000_000_000))})
}
start := time.Now()
parent, weight := GomoryHu(n, edges)
fmt.Printf(" Gomory-Hu (%d max-flows) took %v\n", n-1, time.Since(start))
// spot-check a handful of pairs against Edmonds-Karp
checkStart := time.Now()
for k := 0; k < 5; k++ {
s := rng.Intn(n)
t := rng.Intn(n)
if s == t {
t = (t + 1) % n
}
got := TreePathMin(n, parent, weight, s, t)
ek := EdmondsKarpMinCut(n, edges, s, t)
if got != ek {
fmt.Printf("FAIL bench pair (%d,%d): gh=%d ek=%d\n", s, t, got, ek)
os.Exit(1)
}
}
fmt.Printf(" 5 spot checks vs Edmonds-Karp: OK (%v)\n", time.Since(checkStart))
}
| Test | Method | Scope |
|---|---|---|
| Tiny random graphs | Exhaustive subset enumeration and Edmonds–Karp | every pair, 300 graphs, n = 2..9 |
| Random sparse subgraphs | Independent Edmonds–Karp max-flow | every pair, 40 graphs, n = 20..79, caps up to 1e12 |
| Edge cases | Edmonds–Karp | parallel edges, self-loops, disconnected, 1e12 caps, zero caps |
| Scale test | Timing + spot checks vs Edmonds–Karp | n = 2000, m = 20000, caps up to 1e12 |
Edmonds–Karp is a deliberately different algorithm (BFS augmenting paths, no level graph, no scaling), so agreement is strong evidence of correctness. Brute force enumerates all 2^n cuts, giving an implementation-independent ground truth on tiny inputs.
$ go run . test
== randomized correctness tests ==
tiny graphs vs brute force + Edmonds-Karp: OK
medium sparse graphs vs Edmonds-Karp: OK
edge cases (multi/self/disconnected/1e12/zero): OK
$ go run . bench
== performance (n=2000, m=20000, caps up to 1e12) ==
Gomory-Hu (1999 max-flows) took 10.010526275s
5 spot checks vs Edmonds-Karp: OK (22.291247ms)
mkdir gh && cd gh && go mod init gh
# paste the program above as main.go
go vet ./...
go run . test
go run . bench
n-1 max-flow calls.⌈log2(maxCap)⌉ + 1 ≤ 41 scaling phases per call; within a phase, Dinic computes blocking flows on the delta-residual graph.O(n + m) arcs, rebuilt from the edge list each call — simple and safe; the whole run for n=2000, m=20000 stays around 10s.≤ 2e16; sentinel 2^62 ≈ 4.6e18; int64 max ≈ 9.22e18. All arithmetic is comfortably within range.Verification of the embedded code itself: I extracted the go block from solution.md into a clean module, ran go vet and go run . test, and it passed all three test groups. Files are at ~/solution.md (deliverable) and ~/gh/ (working module).
# Evidence - Problem class: go-gomory-hu-all-pairs-mincut-dinic-scaling - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-03T22:07:54.078Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given an undirected weighted graph with up to 2000 vertices and 20000 edges, compute the full Gomory-Hu cut tree so the minimum s-t cut value for every vertex pair equals the minimum edge weight along the tree path. Implement Dinic's max-flow with capacity scaling plus the Gusfield simplification, handling integer capacities up to 1e12 without overflow. Return the tree edges and prove correctness by cross-checking every pair against an independent min-cut computed on random sparse subgraphs.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-gomory-hu-all-pairs-mincut-dinic-scaling", "provider": "openrouter", "solved_at": "2026-10-03T22:07:54.078Z", "version": "1.26"}