結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー qwewe
提出日時 2025-05-14 12:47:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,070 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 81,720 KB
実行使用メモリ 123,816 KB
最終ジャッジ日時 2025-05-14 12:49:13
合計ジャッジ時間 4,775 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

sys.setrecursionlimit(1 << 25)

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

    # Check底图是否连通
    visited = [False]*(N+1)
    from collections import deque
    # Build无向图的邻接表
    undir_adj = [[] for _ in range(N+1)]
    for u, v in edges:
        undir_adj[u].append(v)
        undir_adj[v].append(u)
    # 找到第一个有边的顶点
    start = -1
    for u in range(1, N+1):
        if len(undir_adj[u]) >0:
            start = u
            break
    if start == -1:
        # 所有顶点都是孤立的，只有0条边，必须添加0条边，因为M=0，此时需要0条边形成欧拉路径
        print(0 if M ==0 else -1)
        return
    # BFS
    q = deque()
    q.append(start)
    visited[start] = True
    while q:
        u = q.popleft()
        for v in undir_adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
    # 检查是否所有有边的顶点都被访问过
    # 孤立的顶点（没有边）可以忽略
    for u in range(1, N+1):
        if len(undir_adj[u]) >0 and not visited[u]:
            # 底图不连通
            c = 0
            # 计算连通分量数目
            visited_all = [False]*(N+1)
            for uu in range(1, N+1):
                if len(undir_adj[uu]) ==0:
                    visited_all[uu] = True
                    continue
                if not visited_all[uu]:
                    c +=1
                    qq = deque()
                    qq.append(uu)
                    visited_all[uu] = True
                    while qq:
                        node = qq.popleft()
                        for vv in undir_adj[node]:
                            if not visited_all[vv]:
                                visited_all[vv] = True
                                qq.append(vv)
            # 底图的连通分量数目是c
            # 需要添加c-1条边
            # 但无法保证这些边是否能够调整度数差，所以输出-1
            print(-1)
            return

    # 底图连通，现在处理度数差
    # 计算d_i = out_degree[i] - in_degree[i]
    d = []
    sum_abs = 0
    for i in range(1, N+1):
        di = out_degree[i] - in_degree[i]
        d.append(di)
        sum_abs += abs(di)
    # 计算K1和 K2
    K1 = sum(max(0, -di) for di in d)
    S = sum_abs
    if S % 2 != 0:
        K2 = float('inf')
    else:
        if S >=2 and (S-2) %2 ==0:
            K2 = (S-2)//2
        else:
            K2 = float('inf')
    # 检查是否存在两个顶点，使得可以调整到+1和-1
    possible = False
    sum_d = sum(d)
    if sum_d !=0:
        print(-1)
        return
    # 检查是否满足欧拉路径的条件
    # 或者调整后的条件
    # 现在底图连通，所以只需要考虑度数差
    # 计算当前的度数差情况
    plus = 0
    minus =0
    for di in d:
        if di >0:
            plus += di
        elif di <0:
            minus += (-di)
    if plus == minus:
        # 可以形成欧拉路径
        pass
    else:
        pass
    # 现在计算K1和 K2的最小值
    if K2 != float('inf'):
        res = min(K1, K2)
    else:
        res = K1
    # 检查是否存在可能的调整
    # 欧拉路径的条件是：0或 2个顶点的度数差为+1和-1，其余为0
    # 检查当前的度数差是否可能调整到这种情况
    # 或者是否可以通过添加边来调整
    # 现在，底图连通，所以输出res
    print(res if res != float('inf') else -1)

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