結果

問題 No.2914 正閉路検出
ユーザー titia
提出日時 2024-10-29 03:18:49
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,315 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 86,988 KB
最終ジャッジ日時 2024-10-29 03:19:23
合計ジャッジ時間 32,129 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,M=map(int,input().split())

EDGE=[list(map(int,input().split())) for i in range(M)]

Group = [i for i in range(N+1)] # グループ分け
Nodes = [1]*(N+1) # 各グループのノードの数
Weight = [0]*(N+1) # 木の親からnode xまでの距離

def find(x):
    ANS=Weight[x]
    while Group[x] != x:
        x=Group[x]
        ANS+=Weight[x]
    return x,ANS

def Union(x,y,z): # xからyの距離がz
    if find(x)[0] != find(y)[0]:
        if Nodes[find(x)[0]] < Nodes[find(y)[0]]:
            Weight[find(x)[0]]=-z+find(y)[1]-find(x)[1]
            
            Nodes[find(y)[0]] += Nodes[find(x)[0]]
            Nodes[find(x)[0]] = 0
            Group[find(x)[0]] = find(y)[0]
            
        else:
            Weight[find(y)[0]]=z+find(x)[1]-find(y)[1]
            
            Nodes[find(x)[0]] += Nodes[find(y)[0]]
            Nodes[find(y)[0]] = 0
            Group[find(y)[0]] = find(x)[0]

E=[[] for i in range(N+1)]
x0,y0=-1,-1

for i in range(M):
    x,y,w = EDGE[i]
    if find(x)[0]!=find(y)[0]:
        Union(x,y,w)
        E[x].append((y,w,i+1))
        E[y].append((x,-w,i+1))
    else:
        kx=find(x)[1]
        ky=find(y)[1]

        if ky-kx==w:
            pass
        else:
            x0,y0=x,y
            last=i+1
            lastw=w

if x0==-1 and y0==-1:
    print(-1)
    exit()

now=x0
ANS=[]
USE=[0]*(N+1)
USE[now]=1
Q=[now]
FROM=[-1]*(N+1)
C=[0]*(N+1)

while Q:
    x=Q.pop()

    for to,cost,ind in E[x]:
        if USE[to]==0:
            FROM[to]=(x,ind)
            C[to]=C[x]+cost
            Q.append(to)
            USE[to]=1
            
ANS=[]

now=y0
while now!=x0:
    fr,ind=FROM[now]
    ANS.append(ind)
    now=fr

if C[y0]-lastw<0:
    print(len(ANS)+1)
    print(x0)
    print(*[last]+ANS)
else:
    print(len(ANS)+1)
    print(x0)
    print(*([last]+ANS)[::-1])
0