模块 4 · NP 理论、网络流、近似算法 与 考试要点

def edmonds_karp(capacities, source, sink):
    """有向图容量矩阵最大流，允许整数容量。Edmonds–Karp O(VE²)。"""
    n = len(capacities)
    if not n or source == sink or not 0 <= source < n or not 0 <= sink < n:
        raise ValueError('源汇不合法')
    if any(len(row) != n or any(c < 0 or not isinstance(c, int) for c in row) for row in capacities):
        raise ValueError('容量须非负整数方阵')
    res = [list(row) for row in capacities]
    total = 0
    while True:
        parent = [-1] * n
        parent[source] = source
        todo = deque([source])
        while todo and parent[sink] == -1:
            u = todo.popleft()
            for v, c in enumerate(res[u]):
                if c > 0 and parent[v] == -1:
                    parent[v] = u
                    todo.append(v)
                    if v == sink:
                        break
        if parent[sink] == -1:
            break
        v = sink
        delta = float('inf')
        while v != source:
            u = parent[v]
            delta = min(delta, res[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            res[u][v] -= delta
            res[v][u] += delta
            v = u
        total += delta
    return total

def vertex_cover_approx(edges):
    """极大匹配 2-近似顶点覆盖算法。O(V + E) 时间，近似比 ρ = 2。"""
    covered = set()
    cover = []
    for u, v in edges:
        if u not in covered and v not in covered:
            covered.add(u)
            covered.add(v)
            cover.extend([u, v])
    return cover