All-Pairs Shortest Paths, Greedy & MST

import heapq
from math import inf

# ── FLOYD-WARSHALL ── O(V^3) ─────────────────────────────────────────
def floyd_warshall(n, edges):
    """
    APSP via Floyd-Warshall. O(V^3) time, O(V^2) space.
    n: number of vertices (0-indexed).
    edges: list of (u, v, w).
    Returns dist[u][v] = delta(u,v), or -inf if negative cycle reachable.
    """
    dist = [[inf]*n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # handle multi-edges

    # Relax through intermediate vertex k
    for k in range(n):
        for u in range(n):
            for v in range(n):
                if dist[u][k] + dist[k][v] < dist[u][v]:
                    dist[u][v] = dist[u][k] + dist[k][v]

    # Detect negative cycles: dist[u][u] < 0 for some u
    has_neg_cycle = any(dist[i][i] < 0 for i in range(n))
    return dist, has_neg_cycle


# ── JOHNSON'S ALGORITHM ── O(VE + V^2 log V) ─────────────────────────
def bellman_ford(n, edges, src):
    """Bellman-Ford from src. Returns (dist, has_negative_cycle)."""
    dist = [inf] * n
    dist[src] = 0
    for _ in range(n - 1):           # n-1 relaxation passes
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return dist, True
    return dist, False

def dijkstra(n, adj, src):
    """Dijkstra with binary heap. O((V+E) log V)."""
    dist = [inf] * n
    dist[src] = 0
    pq = [(0, src)]                   # (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def johnsons(n, edges):
    """
    Johnson's APSP. O(VE + V^2 log V).
    Best for sparse graphs with negative weights.
    """
    # Step 1: Add virtual source s=n, edges (n->v, 0) for all v
    aug_edges = edges + [(n, v, 0) for v in range(n)]
    h, neg_cycle = bellman_ford(n + 1, aug_edges, n)
    if neg_cycle:
        return None, True             # negative cycle detected

    # Step 2: Reweight edges: w_h(u,v) = w(u,v) + h(u) - h(v) >= 0
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        w_h = w + h[u] - h[v]
        adj[u].append((v, w_h))

    # Step 3: Dijkstra from every vertex
    all_dist = []
    for s in range(n):
        d_h = dijkstra(n, adj, s)
        # Recover original distances: delta(s,v) = d_h(s,v) - h(s) + h(v)
        d = [d_h[v] - h[s] + h[v] if d_h[v] < inf else inf
             for v in range(n)]
        all_dist.append(d)
    return all_dist, False

import heapq

# ── PRIM'S MST ── O(E log V) with binary heap ────────────────────────
def prim_mst(n, adj):
    """
    Prim's MST. adj[u] = list of (v, w).
    Grows MST from vertex 0, always adding the min-weight crossing edge.
    Returns (total_weight, mst_edges).
    Uses binary heap: O((V+E) log V).
    Fibonacci heap would give O(E + V log V).
    """
    in_mst = [False] * n
    key     = [float('inf')] * n
    parent  = [-1] * n
    key[0]  = 0
    pq      = [(0, 0)]           # (key, vertex)
    total_w = 0
    mst_edges = []

    while pq:
        w, u = heapq.heappop(pq)
        if in_mst[u]: continue
        in_mst[u] = True
        total_w += w
        if parent[u] != -1:
            mst_edges.append((parent[u], u, w))

        for v, edge_w in adj[u]:
            if not in_mst[v] and edge_w < key[v]:
                key[v]    = edge_w
                parent[v] = u
                heapq.heappush(pq, (edge_w, v))

    return total_w, mst_edges


# ── KRUSKAL'S MST ── O(E log E + E alpha(V)) ─────────────────────────
def kruskal_mst(n, edges):
    """
    Kruskal's MST using Union-Find.
    Sorts edges by weight, adds edge if it connects two different components.
    Returns (total_weight, mst_edges).
    """
    # Union-Find with path compression + union by rank
    parent = list(range(n))
    rank   = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False
        if rank[rx] < rank[ry]: rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]: rank[rx] += 1
        return True

    edges_sorted = sorted(edges, key=lambda e: e[2])
    total_w, mst_edges = 0, []
    for u, v, w in edges_sorted:
        if union(u, v):
            total_w += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break

    return total_w, mst_edges


# ── SPTF PROCESS SCHEDULING ── O(n log n) ────────────────────────────
def sptf_schedule(jobs):
    """
    Shortest Processing Time First: minimise total completion time.
    jobs: list of (job_id, processing_time).
    Returns (schedule, total_completion_time).
    Exchange argument: swapping any two out-of-order adjacent jobs
    strictly decreases total completion time.
    """
    schedule = sorted(jobs, key=lambda j: j[1])   # sort by t_i
    time, total = 0, 0
    for job_id, t in schedule:
        time  += t
        total += time                              # completion time = cumsum
    return schedule, total

import heapq

def min_clones(events):
    """
    Minimum clones needed to attend all events without overlap.
    Greedy: sort by start time, assign to earliest-finishing clone.
    O(n log n): dominated by sort; heap ops O(n log k) where k = answer.

    Correctness: when creating the m-th clone, m events are concurrent
    at that moment => any solution needs >= m clones.
    Connection to Dilworth's theorem: minimum chain partition of a
    partial order (event i <= event j iff i.finish <= j.start)
    equals size of maximum antichain (maximum concurrent events).
    """
    events_sorted = sorted(events, key=lambda e: e[0])  # sort by start
    heap = []  # min-heap of finish times of each clone's last event

    for start, finish in events_sorted:
        if heap and heap[0] <= start:
            # Reuse earliest-finishing clone (it's now free)
            heapq.heapreplace(heap, finish)
        else:
            # No free clone: create a new one
            heapq.heappush(heap, finish)

    return len(heap)   # number of clones = size of heap


def fractional_knapsack(items, capacity):
    """
    Fractional knapsack / fractional make-change.
    items: list of (value_per_unit, max_weight).
    Greedy: take most valuable items first, fractionally if needed.
    O(n log n). Exchange argument proves optimality.
    """
    items_sorted = sorted(items, key=lambda x: -x[0])  # desc value/weight
    total_value, remaining = 0.0, capacity
    selected = []
    for value_rate, max_wt in items_sorted:
        if remaining <= 0: break
        take = min(max_wt, remaining)
        total_value += take * value_rate
        selected.append((value_rate, take))
        remaining -= take
    return total_value, selected

# Example: event partitioning
events = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14)]
print(f"Minimum clones needed: {min_clones(events)}")  # 3