経路圧縮 + size 併合。連結判定 / グループ分け / Kruskal。union は併合したら true。
init 0 1 2 3 4 (各自が根) u(0,1) 0──1 2 3 4 u(2,3) 0──1 2──3 4 u(1,2) 0──1──2──3 4 same(0,3)=T size=4 find: 根まで辿り親を直付け(経路圧縮)
class UnionFind(n: Int) {
val par = IntArray(n) { it }
val sz = IntArray(n) { 1 }
fun find(x: Int): Int {
if (par[x] == x) return x
par[x] = find(par[x]); return par[x]
}
fun union(a: Int, b: Int): Boolean {
var ra = find(a); var rb = find(b)
if (ra == rb) return false
if (sz[ra] < sz[rb]) { val t = ra; ra = rb; rb = t }
par[rb] = ra; sz[ra] += sz[rb]; return true
}
fun same(a: Int, b: Int) = find(a) == find(b)
fun size(x: Int) = sz[find(x)]
}
点加算・前方和を O(log N)。転倒数は「右より小さい既出要素の総数」で求まる。
idx は (i & -i) 幅を管理 add(i,v): x += x & -x で上る sum(i): x -= x & -x で下り a[0..i] の和 区間 [l,r] = sum(r) - sum(l-1) 転倒数: 後ろから add しつつ sum(a[i]-1)
class BIT(val n: Int) {
val t = LongArray(n + 1)
fun add(i: Int, v: Long) {
var x = i + 1
while (x <= n) { t[x] += v; x += x and -x }
}
fun sum(i: Int): Long { // a[0..i]
var x = i + 1; var s = 0L
while (x > 0) { s += t[x]; x -= x and -x }
return s
}
}
fun inversions(a: IntArray): Long {
val bit = BIT((a.maxOrNull() ?: 0) + 1); var res = 0L
for (i in a.indices.reversed()) {
if (a[i] > 0) res += bit.sum(a[i] - 1)
bit.add(a[i], 1)
}
return res
}
優先度キューで未確定のうち最小距離の頂点を順に確定。負辺があると使えない(→Bellman-Ford)。
(0)──5──▶(1) start = 0 │ ▲ init dist=[0, ∞, ∞] 2 1 pop0 1=5 2=2 →[0,5,2] ▼ │ pop2 1=2+1=3 →[0,3,2] (2)───────┘ pop1 settled 0▶1:5 0▶2:2 2▶1:1 ans [0,3,2]
import java.util.PriorityQueue // g[v] = (to, cost) の隣接リスト fun dijkstra(g: Array<MutableList<Pair<Int, Long>>>, s: Int): LongArray { val dist = LongArray(g.size) { Long.MAX_VALUE / 4 }; dist[s] = 0 val pq = PriorityQueue<Pair<Long, Int>>(compareBy { it.first }) pq.add(0L to s) while (pq.isNotEmpty()) { val (d, v) = pq.poll() if (d > dist[v]) continue // 古い距離は捨てる for ((to, c) in g[v]) if (d + c < dist[to]) { dist[to] = d + c; pq.add(dist[to] to to) } } return dist }
4 近傍を距離 +1 で push。壁 # と訪問済みは skip。最短手数 = 到達時の dist。
grid (#=壁) dist from S S . . # 0 1 2 # . # . . 1 # 3 4 . . . G 2 3 4 5 4近傍↑↓←→を BFS → G = 5
val DY = intArrayOf(-1, 1, 0, 0)
val DX = intArrayOf(0, 0, -1, 1)
fun gridBfs(grid: Array<String>, sy: Int, sx: Int): Array<IntArray> {
val h = grid.size; val w = grid[0].length
val dist = Array(h) { IntArray(w) { -1 } }
dist[sy][sx] = 0
val q = ArrayDeque<Int>(); q.add(sy * w + sx)
while (q.isNotEmpty()) {
val p = q.removeFirst(); val y = p / w; val x = p % w
for (d in 0 until 4) {
val ny = y + DY[d]; val nx = x + DX[d]
if (ny !in 0 until h || nx !in 0 until w) continue
if (grid[ny][nx] == '#' || dist[ny][nx] != -1) continue
dist[ny][nx] = dist[y][x] + 1; q.add(ny * w + nx)
}
}
return dist
}
答えの単調性(F..FT..T)で二分。ok=満たす側, ng=満たさない側の初期値を渡す。
pred 単調: F F F T T T
ng ──┬── ok m=(ok+ng)/2
lowerBound: a[i] >= x の最小 i
upperBound: a[i] > x の最小 i
[1 3 3 5 7] x=3 → lower=1 upper=3 個数=2
// pred(ok)=true, pred(ng)=false となる初期値を渡す fun bisect(okInit: Long, ngInit: Long, pred: (Long) -> Boolean): Long { var ok = okInit; var ng = ngInit while (Math.abs(ok - ng) > 1) { val m = (ok + ng) / 2 if (pred(m)) ok = m else ng = m } return ok } fun lowerBound(a: LongArray, x: Long): Int { // a[i] >= x の最小 i var lo = -1; var hi = a.size while (hi - lo > 1) { val m = (lo + hi) / 2; if (a[m] >= x) hi = m else lo = m } return hi } fun upperBound(a: LongArray, x: Long): Int { // a[i] > x の最小 i var lo = -1; var hi = a.size while (hi - lo > 1) { val m = (lo + hi) / 2; if (a[m] > x) hi = m else lo = m } return hi }
累積和で区間和を O(1)。逆操作のいもす法は「区間加算を大量 → 最後に復元」。
a = [1 2 3 4 5]
sum = [0 1 3 6 10 15] (1個ずれ)
区間 [l,r) = sum[r] - sum[l] [1,4)=9
いもす: add(l,r,v)= diff[l]+=v; diff[r]-=v
最後に累積和で復元
fun prefixSum(a: LongArray): LongArray { // s[i]=a[0..i-1]; [l,r)=s[r]-s[l]
val s = LongArray(a.size + 1)
for (i in a.indices) s[i + 1] = s[i] + a[i]
return s
}
class Imos(n: Int) {
val diff = LongArray(n + 1)
fun add(l: Int, r: Int, v: Long) { diff[l] += v; diff[r] -= v } // a[l..r-1]+=v
fun build(): LongArray {
val res = LongArray(diff.size - 1); var acc = 0L
for (i in res.indices) { acc += diff[i]; res[i] = acc }
return res
}
}
modpow は繰返し二乗法。modinv はフェルマー(m素数で a^(m-2))。nCr は階乗逆元の前計算。
modpow(a,e): e を 2 進で繰返し二乗 a^13 = a^8 · a^4 · a^1 (13 = 1101) modinv(a) = a^(m-2) mod m (m 素数) nCr = fact[n]·inv[r]·inv[n-r] 前計算 O(n)
const val MOD = 998244353L // or 1_000_000_007L fun modpow(a: Long, e: Long, m: Long = MOD): Long { var b = a % m; var x = e; var r = 1L while (x > 0) { if (x and 1L == 1L) r = r * b % m; b = b * b % m; x = x shr 1 } return r } fun modinv(a: Long, m: Long = MOD) = modpow(a, m - 2, m) // m は素数 class Comb(maxN: Int, val m: Long = MOD) { val fact = LongArray(maxN + 1); val inv = LongArray(maxN + 1) init { fact[0] = 1 for (i in 1..maxN) fact[i] = fact[i - 1] * i % m inv[maxN] = modpow(fact[maxN], m - 2, m) for (i in maxN downTo 1) inv[i - 1] = inv[i] * i % m } fun nCr(n: Int, r: Int) = if (r < 0 || r > n) 0 else fact[n] * inv[r] % m * inv[n - r] % m }
isPrime[i] を一括計算。i*i から消すのがポイント。約数/素因数のクエリが多いなら最小素因数表へ。
2 3 4 5 6 7 8 9 10 ... 2の倍数除外 → 3の → 5の → ... 消す開始は i*i (それ未満は既出) 残り = 素数 例) ~20: 2 3 5 7 11 13 17 19
fun sieve(n: Int): BooleanArray { // isPrime[i]
val p = BooleanArray(n + 1) { it >= 2 }
var i = 2
while (i * i <= n) {
if (p[i]) { var j = i * i; while (j <= n) { p[j] = false; j += i } }
i++
}
return p
}
gcd は互除法。lcm は先に割って溢れ防止。extGcd は ax+by=gcd の (x,y) も求める(mod 逆元・不定方程式)。
gcd(a,b) = gcd(b, a%b), gcd(a,0)=a gcd(12,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6 lcm = a / gcd · b (先に割る) extGcd: ax + by = gcd の x,y も返す
tailrec fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
// ax + by = gcd(a,b) の (g, x, y)
fun extGcd(a: Long, b: Long): Triple<Long, Long, Long> {
if (b == 0L) return Triple(a, 1L, 0L)
val (g, x, y) = extGcd(b, a % b)
return Triple(g, y, x - (a / b) * y)
}
容量ごとの最大価値。0-1 は重さを逆順ループ(各品物1回)。部分和は価値の代わりに可否を持つ。
品物(w,v), 容量cap. dp[w]=容量wの最大価値 for 品物: for w = cap .. wi (逆順!): dp[w] = max(dp[w], dp[w-wi] + vi) 逆順=各品物1回。正順だと無制限個 部分和: dp[s] = s を作れるか (bool)
// 0-1: 各品物 1 個まで fun knapsack01(w: IntArray, v: LongArray, cap: Int): Long { val dp = LongArray(cap + 1) for (i in w.indices) for (j in cap downTo w[i]) // 重さ逆順 dp[j] = maxOf(dp[j], dp[j - w[i]] + v[i]) return dp[cap] } fun subsetSum(a: IntArray, target: Int): Boolean { val dp = BooleanArray(target + 1); dp[0] = true for (x in a) for (s in target downTo x) if (dp[s - x]) dp[s] = true return dp[target] }
非再帰・抽象化。op はモノイド(結合的 + 単位元 unit)。min/max/和などを区間で。
[5 3 7 1 9] を min セグ木に
[1] ← 全体 min
[3] [9]
[3][7] [9][∞]
[5][3][7][1][9]
update(i,v): 葉→根 query[l,r): 両端から畳む
// op はモノイド(結合的 + 単位元 unit). 例: min/max/和 class SegTree<T>(n: Int, val unit: T, val op: (T, T) -> T) { var size = 1 init { while (size < n) size *= 2 } val t = MutableList(2 * size) { unit } fun update(i: Int, v: T) { var x = i + size; t[x] = v while (x > 1) { x /= 2; t[x] = op(t[2 * x], t[2 * x + 1]) } } fun query(l: Int, r: Int): T { // [l, r) var res = unit; var lo = l + size; var hi = r + size while (lo < hi) { if (lo and 1 == 1) res = op(res, t[lo++]) if (hi and 1 == 1) res = op(res, t[--hi]) lo /= 2; hi /= 2 } return res } }
値の大小を保ったまま 0..k-1 に詰める。BIT/セグ木に乗せる前処理、値の種類数。
a = [100 50 100 7] sort & distinct = [7 50 100] (→ 0 1 2) comp = [ 2 1 2 0] 逆引き: 圧縮値 i → vals[i] が元の値
// 値の大小を保ち 0..k-1 に圧縮。(圧縮後, 元の値配列) を返す
fun compress(a: LongArray): Pair<IntArray, LongArray> {
val vals = a.toSortedSet().toLongArray()
val idx = HashMap<Long, Int>()
for ((i, v) in vals.withIndex()) idx[v] = i
return IntArray(a.size) { idx[a[it]]!! } to vals
}
全辺を n-1 回緩和。負辺 OK。n 回目でも更新できれば負閉路。Dijkstra が使えない時に。
全辺を n-1 回 緩和(relax) dist[t] = min(dist[t], dist[f] + cost) n 回目でも更新 → 負閉路あり 始点から到達する負閉路だけが検出対象
data class Edge(val from: Int, val to: Int, val cost: Long) // 負辺ありの単一始点最短路 O(VE)。負閉路があれば null fun bellmanFord(n: Int, edges: List<Edge>, s: Int): LongArray? { val INF = Long.MAX_VALUE / 4 val dist = LongArray(n) { INF }; dist[s] = 0 repeat(n - 1) { for ((f, t, c) in edges) if (dist[f] != INF && dist[f] + c < dist[t]) dist[t] = dist[f] + c } for ((f, t, c) in edges) if (dist[f] != INF && dist[f] + c < dist[t]) return null // 負閉路 return dist }
中継点 k を全部試す DP。V≤500 まで。負辺 OK(負閉路は dist[v][v]<0 で検出)。
中継点 k = 0..n-1 を全部試す dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 隣接行列(辺なし=INF, 対角0)を渡し in-place 更新 ループ順は k, i, j の順 (k が最外)
// 全点対最短路。dist は隣接行列(辺なし=INF, 対角0) を in-place 更新
fun warshallFloyd(dist: Array<LongArray>) {
val INF = Long.MAX_VALUE / 4; val n = dist.size
for (k in 0 until n) for (i in 0 until n) {
if (dist[i][k] == INF) continue
for (j in 0 until n)
if (dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j]
}
}
入次数 0 をキューから取り出し、辺を消しながら並べる。全頂点出せなければ閉路。
入次数0をキューへ → 取り出しつつ出る辺を消す (消した先の入次数が0になったら追加) 全頂点出れば順序確定 / 出きらねば閉路 辞書順最小が要るなら queue → 優先度付き
// Kahn 法。g: 隣接リスト(有向). 閉路があれば null
fun topoSort(g: Array<MutableList<Int>>): List<Int>? {
val n = g.size; val indeg = IntArray(n)
for (v in 0 until n) for (to in g[v]) indeg[to]++
val q = ArrayDeque<Int>()
for (v in 0 until n) if (indeg[v] == 0) q.add(v)
val order = mutableListOf<Int>()
while (q.isNotEmpty()) {
val v = q.removeFirst(); order.add(v)
for (to in g[v]) if (--indeg[to] == 0) q.add(to)
}
return if (order.size == n) order else null
}
辺を cost 昇順に見て、端点が別グループなら採用(Union-Find)。全部つなぐ最小コスト。
辺を cost 昇順にソート 端点が別グループなら採用(UnionFind で併合) 採用辺が n-1 本で全域木 完成 ※ Union-Find のスニペットが必要
data class WEdge(val u: Int, val v: Int, val cost: Long)
// 最小全域木。UnionFind が必要。総コスト(非連結なら null)
fun kruskal(n: Int, edges: List<WEdge>): Long? {
val uf = UnionFind(n); var total = 0L; var used = 0
for ((u, v, c) in edges.sortedBy { it.cost })
if (uf.union(u, v)) { total += c; used++ }
return if (used == n - 1) total else null
}
窓 [left,right] を右に伸ばし、条件を破ったら左を詰める。単調性が前提(非負配列など)。
[left,right] 窓を右へ伸ばし、破ったら左を詰める 和<=k 最大長: 超えたら left++ で縮める 和>=k 個数: 初めて満たせば右端以降は全部OK 単調性(伸ばすと悪化/縮めると改善)が必要
// 和が k 以下の連続区間の最大長 (a は非負) fun longestAtMost(a: LongArray, k: Long): Int { var best = 0; var sum = 0L; var left = 0 for (right in a.indices) { sum += a[right] while (sum > k) { sum -= a[left]; left++ } best = maxOf(best, right - left + 1) } return best } // 和が k 以上の連続区間の総数 (a は非負) fun countAtLeast(a: LongArray, k: Long): Long { val n = a.size; var count = 0L; var sum = 0L; var right = 0 for (left in 0 until n) { while (right < n && sum < k) { sum += a[right]; right++ } if (sum < k) break count += n - right + 1 sum -= a[left] } return count }
bit 全探索で選ぶ/選ばない 2ⁿ 通り(n≤20)。next permutation で全順列(n≤10)。
bit全探索: mask 0..2^n-1, i bit目で i 番目採用 for mask: for i: if (mask>>i & 1) use i 順列: 末尾から増加位置を探し交換→反転 012 021 102 120 201 210 (n! 通り)
// bit 全探索: for (mask in 0 until (1 shl n)) { (mask shr i and 1) ... } // 辞書順で次の順列に in-place。なければ false。do{}while で全列挙 fun nextPermutation(a: IntArray): Boolean { var i = a.size - 2 while (i >= 0 && a[i] >= a[i + 1]) i-- if (i < 0) return false var j = a.size - 1 while (a[j] <= a[i]) j-- a[i] = a[j].also { a[j] = a[i] } var lo = i + 1; var hi = a.size - 1 while (lo < hi) { a[lo] = a[hi].also { a[hi] = a[lo] }; lo++; hi-- } return true }
LIS は末尾最小値を二分探索で更新。LCS・編集距離は 2 次元 DP 表。
LIS: tail[k] = 長さ k+1 の増加列の末尾の最小値 各 x を lower_bound で 置換 or 追加 → 長さが答え LCS/編集距離: dp[i][j] を表で 一致なら \+1 / 不一致は周囲の最小から
// LIS (最長増加部分列) O(N log N) fun lis(a: IntArray): Int { val tail = mutableListOf<Int>() for (x in a) { val pos = tail.binarySearch(x).let { if (it < 0) -(it + 1) else it } if (pos == tail.size) tail.add(x) else tail[pos] = x } return tail.size } // LCS (最長共通部分列) O(NM) fun lcs(s: String, t: String): Int { val dp = Array(s.length + 1) { IntArray(t.length + 1) } for (i in s.indices) for (j in t.indices) dp[i + 1][j + 1] = if (s[i] == t[j]) dp[i][j] + 1 else maxOf(dp[i][j + 1], dp[i + 1][j]) return dp[s.length][t.length] } // 編集距離 (Levenshtein) O(NM) fun editDistance(s: String, t: String): Int { val dp = Array(s.length + 1) { IntArray(t.length + 1) } for (i in 0..s.length) dp[i][0] = i for (j in 0..t.length) dp[0][j] = j for (i in 1..s.length) for (j in 1..t.length) { val c = if (s[i - 1] == t[j - 1]) 0 else 1 dp[i][j] = minOf(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + c) } return dp[s.length][t.length] }
p=2 から割り続ける素因数分解。約数は d と n/d をペアで集める。素数判定も同様。
factorize: p=2.. (p*p<=v) の間割り続ける 残った v>1 は最大の素因数 360 = 2^3 · 3^2 · 5 divisors: d*d<=n, n%d==0 で d と n/d を集める 12 の約数 = 1 2 3 4 6 12
// 素因数分解 {素因数: 指数} O(√N) fun factorize(n: Long): Map<Long, Int> { val res = LinkedHashMap<Long, Int>(); var v = n; var p = 2L while (p * p <= v) { while (v % p == 0L) { res[p] = (res[p] ?: 0) + 1; v /= p }; p++ } if (v > 1) res[v] = (res[v] ?: 0) + 1 return res } // 約数列挙 (ソート済み) O(√N) fun divisors(n: Long): List<Long> { val small = mutableListOf<Long>(); val large = mutableListOf<Long>(); var d = 1L while (d * d <= n) { if (n % d == 0L) { small.add(d); if (d != n / d) large.add(n / d) } d++ } return small + large.reversed() } fun isPrime(n: Long): Boolean { if (n < 2) return false var d = 2L; while (d * d <= n) { if (n % d == 0L) return false; d++ } return true }
訪問済み集合を bit で持つ DP。N≤16 程度。全頂点を回って戻る最小コスト等。
dp[S][v] = 訪問済み集合 S で今 v にいる最小コスト
0 から出発: dp[{0}][0] = 0
S に未訪問 to を足して遷移
最後に全訪問+0へ戻る最小。N<=16 (2^16·16^2)
// bitDP 巡回セールスマン O(2^N N^2). N<=16 // dist[i][j] = i->j のコスト。0 から全頂点回り 0 に戻る最小 fun tsp(dist: Array<LongArray>): Long { val INF = Long.MAX_VALUE / 4; val n = dist.size; val full = 1 shl n val dp = Array(full) { LongArray(n) { INF } } dp[1][0] = 0 for (s in 0 until full) for (v in 0 until n) { if (dp[s][v] == INF) continue for (to in 0 until n) { if (s shr to and 1 == 1) continue val ns = s or (1 shl to) if (dp[s][v] + dist[v][to] < dp[ns][to]) dp[ns][to] = dp[s][v] + dist[v][to] } } var res = INF for (v in 1 until n) if (dp[full - 1][v] != INF) res = minOf(res, dp[full - 1][v] + dist[v][0]) return res }
文字列を多項式ハッシュに。mod 2⁶¹-1 で衝突回避。部分文字列の一致判定が O(1)。
h[i] = s[0..i-1] の多項式ハッシュ (base 進数) get(l,r) = h[r] - h[l]·base^(r-l) (mod 2^61-1) 部分文字列が等しい ⇔ ハッシュ一致 (O(1)) base はランダム、mod は 2^61-1 が安全
// ローリングハッシュ (mod 2^61-1)。部分文字列比較 O(1) class RollingHash(s: String) { val MOD = (1L shl 61) - 1 val BASE = 1_000_003L val h = LongArray(s.length + 1) val pw = LongArray(s.length + 1) init { pw[0] = 1 for (i in s.indices) { h[i + 1] = mul(h[i], BASE) + s[i].code if (h[i + 1] >= MOD) h[i + 1] -= MOD pw[i + 1] = mul(pw[i], BASE) } } fun mul(a: Long, b: Long): Long { // a*b mod (2^61-1) val hi = Math.multiplyHigh(a, b); val lo = a * b var r = (hi shl 3) + (lo ushr 61) + (lo and MOD) if (r >= MOD) r -= MOD return r } fun get(l: Int, r: Int): Long { // [l, r) var res = h[r] - mul(h[l], pw[r - l]) if (res < 0) res += MOD return res } }
ccw(外積で回転方向)が基礎。線分交差・凸包・面積。誤差は EPS で比較、整数なら Long で。
ccw(a,b,c): 外積の符号で回転方向 1:反時計 -1:時計 0/±2:一直線上 線分交差: 互いに相手を挟む ⇔ 交差 凸包(Andrew): x昇順→下側→上側 cross<EPS で pop (左折だけ残す=反時計回り)
const val EPS = 1e-9
class P(val x: Double, val y: Double) {
operator fun minus(o: P) = P(x - o.x, y - o.y)
fun cross(o: P) = x * o.y - y * o.x
fun dot(o: P) = x * o.x + y * o.y
}
// 1:反時計 -1:時計 2:c-a-b -2:a-b-c 0:線分ab上
fun ccw(a: P, b: P, c: P): Int {
val ab = b - a; val ac = c - a
return when {
ab.cross(ac) > EPS -> 1
ab.cross(ac) < -EPS -> -1
ab.dot(ac) < -EPS -> 2
ab.dot(ab) < ac.dot(ac) - EPS -> -2
else -> 0
}
}
fun segIntersect(a: P, b: P, c: P, d: P): Boolean =
ccw(a, b, c) * ccw(a, b, d) <= 0 && ccw(c, d, a) * ccw(c, d, b) <= 0
// 凸包(反時計回り) O(N log N)
fun convexHull(ps: List<P>): List<P> {
val s = ps.sortedWith(compareBy({ it.x }, { it.y }))
if (s.size <= 2) return s
val h = mutableListOf<P>()
fun build(floor: Int, pts: List<P>) {
for (p in pts) {
while (h.size > floor &&
(h[h.size - 1] - h[h.size - 2]).cross(p - h[h.size - 1]) < EPS)
h.removeAt(h.size - 1)
h.add(p)
}
}
build(1, s); val lower = h.size; build(lower, s.reversed().drop(1))
return h.dropLast(1)
}
// 符号付き面積(反時計回りで正)
fun polygonArea(poly: List<P>): Double {
var s = 0.0
for (i in poly.indices) s += poly[i].cross(poly[(i + 1) % poly.size])
return s / 2
}
左頂点から増加路を DFS で探す。割り当て問題、最大マッチング = 最小頂点被覆(König)。
左→右の辺。各左頂点から増加路を DFS 右が空 or その相手を押し出せれば マッチ確定 最大マッチング数 = 最小頂点被覆 (König の定理) used[] を頂点ごとにリセットして探索
// 増加路 DFS O(VE)。左 n, 右 m。addEdge 後 solve()
class BipartiteMatching(val n: Int, val m: Int) {
val g = Array(n) { mutableListOf<Int>() }
val matchR = IntArray(m) { -1 }
fun addEdge(u: Int, v: Int) { g[u].add(v) }
fun dfs(u: Int, used: BooleanArray): Boolean {
for (v in g[u]) {
if (used[v]) continue
used[v] = true
if (matchR[v] == -1 || dfs(matchR[v], used)) { matchR[v] = u; return true }
}
return false
}
fun solve(): Int {
var res = 0
for (u in 0 until n) if (dfs(u, BooleanArray(m))) res++
return res
}
}
BFS でレベル分けし、レベル順に DFS で流す。最大流・最小カット・二部マッチングに。
BFS でレベル(最短距離)を付ける → レベルが増える辺だけ DFS で流す 逆辺(rev)に流量を戻し増加路を表現。繰り返す 最大流 = 最小カット。「同時不可の最小除去」に
// Dinic 最大流 O(V^2 E)。最大流=最小カット
class Dinic(val n: Int) {
class E(val to: Int, var cap: Long, val rev: Int)
val g = Array(n) { mutableListOf<E>() }
val level = IntArray(n); val iter = IntArray(n)
fun addEdge(from: Int, to: Int, cap: Long) {
g[from].add(E(to, cap, g[to].size))
g[to].add(E(from, 0, g[from].size - 1))
}
fun bfs(s: Int) {
level.fill(-1); level[s] = 0
val q = ArrayDeque<Int>(); q.add(s)
while (q.isNotEmpty()) {
val v = q.removeFirst()
for (e in g[v]) if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.add(e.to) }
}
}
fun dfs(v: Int, t: Int, f: Long): Long {
if (v == t) return f
while (iter[v] < g[v].size) {
val e = g[v][iter[v]]
if (e.cap > 0 && level[v] < level[e.to]) {
val d = dfs(e.to, t, minOf(f, e.cap))
if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d }
}
iter[v]++
}
return 0
}
fun maxFlow(s: Int, t: Int): Long {
var flow = 0L
while (true) {
bfs(s); if (level[t] < 0) return flow
iter.fill(0)
while (true) { val f = dfs(s, t, Long.MAX_VALUE / 4); if (f == 0L) break; flow += f }
}
}
}