最大流

  1type edge struct{ from, to, cap, flow int }
  2type _edge struct{ to, cap, rev int }
  3type maxFlow struct {
  4	g    [][]_edge
  5	es   [][2]int
  6	lv   []int
  7	iter []int
  8}
  9
 10func newMaxFlow(n int) *maxFlow {
 11	return &maxFlow{make([][]_edge, n), [][2]int{}, make([]int, n), make([]int, n)}
 12}
 13
 14func (mf *maxFlow) AddEdge(from, to, cap int) {
 15	mf.es = append(mf.es, [2]int{from, len(mf.g[from])})
 16	mf.g[from] = append(mf.g[from], _edge{to, cap, len(mf.g[to])})
 17	mf.g[to] = append(mf.g[to], _edge{from, 0, len(mf.g[from]) - 1})
 18}
 19
 20func (mf *maxFlow) Edge(i int) edge {
 21	v := mf.es[i]
 22	e := mf.g[v[0]][v[1]]
 23	r := mf.g[e.to][e.rev]
 24	return edge{v[0], e.to, e.cap + r.cap, r.cap}
 25}
 26
 27func (mf *maxFlow) Edges() []edge {
 28	es := []edge{}
 29	for i := 0; i < len(mf.es); i++ {
 30		es = append(es, mf.Edge(i))
 31	}
 32	return es
 33}
 34
 35func (mf *maxFlow) bfs(s int) {
 36	for i := 0; i < len(mf.g); i++ {
 37		mf.lv[i] = -1
 38	}
 39	mf.lv[s] = 0
 40	q := []int{s}
 41	for len(q) != 0 {
 42		v := q[0]
 43		q = q[1:]
 44		for _, e := range mf.g[v] {
 45			if e.cap == 0 || mf.lv[e.to] >= 0 {
 46				continue
 47			}
 48			mf.lv[e.to] = mf.lv[v] + 1
 49			q = append(q, e.to)
 50		}
 51	}
 52}
 53
 54func (mf *maxFlow) dfs(v, t, f int) int {
 55	if v == t {
 56		return f
 57	}
 58
 59	for i := &mf.iter[v]; *i < len(mf.g[v]); *i++ {
 60		e := &mf.g[v][*i]
 61		if e.cap == 0 || mf.lv[v] >= mf.lv[e.to] {
 62			continue
 63		}
 64		mi := f
 65		if mi > e.cap {
 66			mi = e.cap
 67		}
 68		if d := mf.dfs(e.to, t, mi); d > 0 {
 69			e.cap -= d
 70			mf.g[e.to][e.rev].cap += d
 71			return d
 72		}
 73	}
 74	return 0
 75}
 76
 77func (mf *maxFlow) Flow(s, t, inf int) int {
 78	flow := 0
 79	for {
 80		mf.bfs(s)
 81		if mf.lv[t] < 0 {
 82			return flow
 83		}
 84		for i := 0; i < len(mf.g); i++ {
 85			mf.iter[i] = 0
 86		}
 87		for {
 88			f := mf.dfs(s, t, inf)
 89			if f == 0 {
 90				break
 91			}
 92			flow += f
 93		}
 94	}
 95}
 96
 97func (mf *maxFlow) MinCut(s int) []bool {
 98	vis := make([]bool, len(mf.g))
 99	q := []int{s}
100	for len(q) != 0 {
101		p := q[0]
102		q = q[1:]
103		for _, e := range mf.g[p] {
104			if e.cap != 0 && !vis[e.to] {
105				vis[e.to] = true
106				q = append(q, e.to)
107			}
108		}
109	}
110	return vis
111}