Day 042-Q4 — 最大密度部分グラフ（Goldberg / 二分探索 + 最大流）

2026-05-25 赤色 Master / Phase 8+ ★★★★★★★★★ Densest Subgraph / Parametric Flow

問題

$N$ 頂点 $M$ 辺の無向グラフで、部分集合 $S \subseteq V$（$S \neq \emptyset$）の密度を $\rho(S) = |E(S)| / |S|$ と定義する。密度の最大値 $\rho^*$ を有理数で出力せよ。

制約

$1 \le N \le 500$
$1 \le M \le 2000$
時間制限: 3sec / メモリ: 256MB

入出力例

入力例 1

5 6
1 2
1 3
2 3
2 4
3 5
4 5

出力例 1

1/1

三角形 {1,2,3} は 3辺/3頂点 = 1.0。

概念図: 密度最大化のフロー構成

s v₁ v₂ v₃ t deg(v₁)/2+g deg(v₂)/2+g deg(v₃)/2+g deg(v₁)/2 deg(v₂)/2 deg(v₃)/2 判定: g が密度上限か？ 最大流 ≥ 総ソース容量 → ρ* ≤ g → ρ* > g なら密部分グラフあり

ヒント（段階的開示）

ヒント1: 方向性
密度 $\rho(S) = |E(S)|/|S|$ を直接最適化するのは難しい。Goldberg のアルゴリズムは「$\rho(S) > g$ となる $S$ が存在するか？」を最大流で判定し、二分探索で $\rho^*$ を求める。
ヒント2: アプローチ
  1. 判定 threshold $g$ に対してフローネットワークを構成。
  2. $s \to v$: 容量 $\deg(v)/2 + g$、$v \to t$: 容量 $\deg(v)/2$、辺 $(u,v)$: $u \leftrightarrow v$ 各容量 1。
  3. 最大流が総 $s$-出力容量 $\sum(\deg(v)/2 + g)$ に等しい iff $\rho^* \le g$。
  4. 二分探索で $g$ を絞り込み、最後に Fraction で有理数化。
ヒント3: 実装骨格 
def check(g):
    # g が密度上限か判定
    mf = MaxFlow(N + 2)
    s, t = N, N + 1
    total_cap = 0
    for u, v in edges:
        mf.add_edge(u, v, 1)
        mf.add_edge(v, u, 1)
    for v in range(N):
        sv_cap = deg[v] / 2 + g
        mf.add_edge(s, v, sv_cap)
        mf.add_edge(v, t, deg[v] / 2)
        total_cap += sv_cap
    return mf.max_flow(s, t) >= total_cap - 1e-9

lo, hi = 0.0, M
for _ in range(100):
    mid = (lo + hi) / 2
    if check(mid): hi = mid
    else: lo = mid

模範解答 (Python)

import sys
from collections import deque
from fractions import Fraction

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1]); idx += 2
    edges = []
    deg = [0] * N
    for _ in range(M):
        u, v = int(data[idx])-1, int(data[idx+1])-1; idx += 2
        edges.append((u, v))
        deg[u] += 1; deg[v] += 1

    class MaxFlow:
        def __init__(self, n):
            self.n = n
            self.graph = [[] for _ in range(n)]
        def add_edge(self, u, v, cap):
            self.graph[u].append([v, cap, len(self.graph[v])])
            self.graph[v].append([u, 0.0, len(self.graph[u])-1])
        def bfs(self, s, t):
            self.level = [-1]*self.n; self.level[s] = 0
            q = deque([s])
            while q:
                v = q.popleft()
                for to, cap, _ in self.graph[v]:
                    if cap > 1e-9 and self.level[to] < 0:
                        self.level[to] = self.level[v]+1; q.append(to)
            return self.level[t] >= 0
        def dfs(self, v, t, f, it):
            if v == t: return f
            while it[v] < len(self.graph[v]):
                to, cap, rev = self.graph[v][it[v]]
                if cap > 1e-9 and self.level[v] < self.level[to]:
                    d = self.dfs(to, t, min(f, cap), it)
                    if d > 1e-12:
                        self.graph[v][it[v]][1] -= d
                        self.graph[to][rev][1] += d
                        return d
                it[v] += 1
            return 0.0
        def max_flow(self, s, t):
            flow = 0.0
            while self.bfs(s, t):
                it = [0]*self.n
                while True:
                    f = self.dfs(s, t, float('inf'), it)
                    if f < 1e-12: break
                    flow += f
            return flow

    def check(g):
        mf = MaxFlow(N + 2)
        s, t = N, N + 1
        total = 0.0
        for u, v in edges:
            mf.add_edge(u, v, 1.0); mf.add_edge(v, u, 1.0)
        for v in range(N):
            cap = deg[v] / 2.0 + g
            mf.add_edge(s, v, cap); mf.add_edge(v, t, deg[v] / 2.0)
            total += cap
        return mf.max_flow(s, t) >= total - 1e-6

    lo, hi = 0.0, float(M)
    for _ in range(100):
        mid = (lo + hi) / 2
        if check(mid): hi = mid
        else: lo = mid

    frac = Fraction(lo).limit_denominator(N * (N-1) // 2 + 1)
    print(f"{frac.numerator}/{frac.denominator}")

solve()

Step-by-Step 解説

1密度最大化の困難さ
$\rho(S) = |E(S)|/|S|$ は比率の最大化であり、整数計画問題。直接解くのは NP 困難に見えるが、グラフの密度最大化は多項式時間で解ける特殊構造を持つ。
2Goldberg の判定フロー
「密度 $> g$ の部分集合が存在するか」を s-t 最大流で判定。$s \to v$ 容量 $\deg(v)/2 + g$、$v \to t$ 容量 $\deg(v)/2$、元の辺は両方向に容量 1。最大流 = 総 $s$-容量なら $\rho^* \le g$。
3二分探索の収束
$g \in [0, M]$ を 100 回二分探索すれば十分な精度（$\approx M/2^{100}$）。最後に `Fraction.limit_denominator` で有理数に復元する。
4最小カットからの部分集合復元
最適 $g$ でのフロー後、$s$ 側の最小カットを BFS/DFS で探索すると最大密度部分集合 $S^*$ が復元できる。

計算量

各判定（Dinic 法）: $O(V^2 E)$
二分探索: $O(\log(M/\varepsilon))$ 回
合計: $O(V^2 E \log(M/\varepsilon))$
$N=500, M=2000$ で実用的に動作

よくあるミス

ミス原因正しい書き方
整数容量で実数を表現Dinic の整数前提スケール（×10^6）するか浮動小数点 Dinic
判定の向き（> vs ≥）等号のケース浮動小数点 EPS を適切に設定
有理数復元の精度不足limit_denominator 上限が小さい分母は最大 $N(N-1)/2$

次のステップ

  • 発展問題: 辺重み付き密度最大化 $|E(S)|_w / |S|$ の最大化
  • 類題: CF 786F "Symmetric dataset"
  • 応用: ソーシャルネットワーク解析・クラスタリング（最大密度コミュニティ検出）

自己評価