Day 171-Q4 — 2026-10-06 | 有向グラフの郵便配達路（入次数と出次数の差を最小費用流で埋め、多重グラフのオイラー閉路を Hierholzer で作る）

📋 コピーimport sys
from heapq import heappush, heappop


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    A = [0] * m; B = [0] * m; C = [0] * m
    bal = [0] * n                                # 入次数 − 出次数
    base = 0
    for e in range(m):
        a, b, c = int(data[2 + 3 * e]) - 1, int(data[3 + 3 * e]) - 1, int(data[4 + 3 * e])
        A[e], B[e], C[e] = a, b, c
        bal[b] += 1
        bal[a] -= 1
        base += c

    # 最小費用流: S → (入 > 出 の頂点) 容量 bal、(出 > 入 の頂点) → T 容量 −bal、元の辺は容量 ∞ で費用 c
    S, T = n, n + 1
    V = n + 2
    to, cap, cost, head, nxt = [], [], [], [-1] * V, []

    def add_edge(u, v, cp, cs):
        for x, y, p, q in ((u, v, cp, cs), (v, u, 0, -cs)):
            to.append(y); cap.append(p); cost.append(q); nxt.append(head[x]); head[x] = len(to) - 1

    INF = 1 << 60
    for e in range(m):
        add_edge(A[e], B[e], INF, C[e])          # 辺 e の順向きは添字 2e
    need = 0
    for v in range(n):
        if bal[v] > 0:
            add_edge(S, v, bal[v], 0)
            need += bal[v]
        elif bal[v] < 0:
            add_edge(v, T, -bal[v], 0)

    h = [0] * V                                  # ポテンシャル（費用は非負なので 0 から始めてよい）
    extra = 0
    flowed = 0
    while flowed < need:
        dist = [INF] * V
        pe = [-1] * V
        dist[S] = 0
        pq = [(0, S)]
        while pq:
            d, u = heappop(pq)
            if d > dist[u]:
                continue
            i = head[u]
            hu = h[u]
            while i != -1:
                if cap[i] > 0:
                    v = to[i]
                    nd = d + cost[i] + hu - h[v]
                    if nd < dist[v]:
                        dist[v] = nd
                        pe[v] = i
                        heappush(pq, (nd, v))
                i = nxt[i]
        for v in range(V):
            if dist[v] < INF:
                h[v] += dist[v]
        # 経路上の最小残余容量だけ流す（内側の辺は ∞ なので、S か T の辺が必ず飽和する）
        f = need - flowed
        v = T
        while v != S:
            i = pe[v]
            if cap[i] < f:
                f = cap[i]
            v = to[i ^ 1]
        v = T
        while v != S:
            i = pe[v]
            cap[i] -= f
            cap[i ^ 1] += f
            v = to[i ^ 1]
        flowed += f
        extra += f * (h[T] - h[S])

    # 各辺を 1 + (流れた量) 回使う多重グラフでオイラー閉路（Hierholzer、反復版）
    rem = [1 + cap[2 * e + 1] for e in range(m)]  # 逆辺の容量 = 流れた量
    out = [[] for _ in range(n)]
    for e in range(m):
        out[A[e]].append(e)
    ptr = [0] * n
    stack = [(0, -1)]                            # (頂点, そこへ来た辺)
    walk = []
    while stack:
        u, e_in = stack[-1]
        lst = out[u]
        while ptr[u] < len(lst) and rem[lst[ptr[u]]] == 0:
            ptr[u] += 1
        if ptr[u] == len(lst):
            stack.pop()
            if e_in >= 0:
                walk.append(e_in)
        else:
            e = lst[ptr[u]]
            rem[e] -= 1
            stack.append((B[e], e))
    walk.reverse()
    sys.stdout.write(f"{base + extra}\n{len(walk)}\n{' '.join(str(e + 1) for e in walk)}\n")


main()