Day 178-Q5 — 2026-10-14 | 最小カットに「必ず入る辺」「入りうる辺」を見分ける（最大流 1 回の残余グラフで、s から届く集合・t へ届く集合・強連結成分の 3 つを見るだけ）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    s, t = 0, n - 1
    # 辺 i は 2i（順向き）と 2i+1（逆向き）。to/cap を平らな配列で持つ
    head = [[] for _ in range(n)]
    to = [0] * (2 * m)
    cap = [0] * (2 * m)
    eu = [0] * m
    ev = [0] * m
    for i in range(m):
        u = int(data[2 + 3 * i]) - 1
        v = int(data[3 + 3 * i]) - 1
        c = int(data[4 + 3 * i])
        eu[i], ev[i] = u, v
        to[2 * i], cap[2 * i] = v, c
        to[2 * i + 1], cap[2 * i + 1] = u, 0
        head[u].append(2 * i)
        head[v].append(2 * i + 1)
    # ---- Dinic
    flow = 0
    while True:
        level = [-1] * n
        level[s] = 0
        dq = deque([s])
        while dq:
            x = dq.popleft()
            for e in head[x]:
                if cap[e] and level[to[e]] < 0:
                    level[to[e]] = level[x] + 1
                    dq.append(to[e])
        if level[t] < 0:
            break
        it = [0] * n
        while True:                        # 反復 DFS で増加路を 1 本ずつ
            path = []
            x = s
            while x != t:
                adv = False
                hx = head[x]
                while it[x] < len(hx):
                    e = hx[it[x]]
                    y = to[e]
                    if cap[e] and level[y] == level[x] + 1:
                        path.append(e)
                        x = y
                        adv = True
                        break
                    it[x] += 1
                if not adv:
                    if x == s:
                        break
                    level[x] = -1          # 行き止まり。以後この頂点は使わない
                    e = path.pop()
                    x = to[e ^ 1]
                    it[x] += 1
            if x != t:
                break
            f = min(cap[e] for e in path)
            for e in path:
                cap[e] -= f
                cap[e ^ 1] += f
            flow += f
    # ---- 残余グラフ: s から届く集合 A、t へ届く集合 B
    A = [False] * n
    A[s] = True
    dq = deque([s])
    while dq:
        x = dq.popleft()
        for e in head[x]:
            if cap[e] and not A[to[e]]:
                A[to[e]] = True
                dq.append(to[e])
    B = [False] * n
    B[t] = True
    dq = deque([t])
    while dq:
        x = dq.popleft()
        for e in head[x]:                  # 残余辺 y→x（= 辺 e^1 の残り容量）を逆にたどる
            y = to[e]
            if cap[e ^ 1] and not B[y]:
                B[y] = True
                dq.append(y)
    # ---- 残余グラフの強連結成分（反復 Tarjan）
    comp = [-1] * n
    idx = [-1] * n
    low = [0] * n
    onst = [False] * n
    st = []
    counter = 0
    nc = 0
    for r in range(n):
        if idx[r] >= 0:
            continue
        work = [(r, 0)]
        idx[r] = low[r] = counter
        counter += 1
        st.append(r)
        onst[r] = True
        while work:
            x, i = work[-1]
            hx = head[x]
            if i < len(hx):
                work[-1] = (x, i + 1)
                e = hx[i]
                if cap[e]:
                    y = to[e]
                    if idx[y] < 0:
                        idx[y] = low[y] = counter
                        counter += 1
                        st.append(y)
                        onst[y] = True
                        work.append((y, 0))
                    elif onst[y] and idx[y] < low[x]:
                        low[x] = idx[y]
                continue
            work.pop()
            if work:
                px = work[-1][0]
                if low[x] < low[px]:
                    low[px] = low[x]
            if low[x] == idx[x]:
                while True:
                    y = st.pop()
                    onst[y] = False
                    comp[y] = nc
                    if y == x:
                        break
                nc += 1
    out = []
    for i in range(m):
        u, v = eu[i], ev[i]
        if cap[2 * i]:                     # 飽和していない辺はどの最小カットにも入らない
            out.append(0)
        elif A[u] and B[v]:
            out.append(2)                  # 最小の S と最大の S の両方をまたぐ → 全部に入る
        elif comp[u] != comp[v]:
            out.append(1)                  # 残余で u から v へ行けない → u を含み v を含まない閉集合がある
        else:
            out.append(0)
    print(flow)
    print(" ".join(map(str, out)))


main()