結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー lam6er
提出日時 2025-04-09 20:56:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,075 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 123,964 KB
最終ジャッジ日時 2025-04-09 20:58:05
合計ジャッジ時間 4,175 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx +=2
    out_degree = [0] * (N+1)
    in_degree = [0] * (N+1)
    for _ in range(M):
        u = int(input[idx])
        v = int(input[idx+1])
        out_degree[u] +=1
        in_degree[v] +=1
        idx +=2

    current_d = [0]*(N+1)
    for i in range(1, N+1):
        current_d[i] = out_degree[i] - in_degree[i]

    K1 = 0
    for d in current_d[1:]:
        K1 += max(0, -d)

    A = []
    B = []
    for i in range(1, N+1):
        d = current_d[i]
        # A(s) = max(0, 1-d) - max(0, -d)
        term1 = max(0, 1 - d) 
        term2 = max(0, -d)
        a = term1 - term2
        A.append(a)
        # B(t) = max(0, -1 -d) - max(0, -d)
        term3 = max(0, -1 - d)
        term4 = max(0, -d)
        b_val = term3 - term4
        B.append(b_val)

    a_min = min(A) if A else 0
    b_min = min(B) if B else 0
    K2 = K1 + a_min + b_min

    ans = min(K1, K2)
    print(ans if ans >=0 else -1)

if __name__ == '__main__':
    main()
0