質問する

Access

質問する

これは問題です.時間が逆流する幹線があるため,幹線値に負の値が存在するため,ベルマンフォードアルゴリズムを用いて負の幹線を計算することは避けられない可能性がある.これは、以前よりも時間が遅いかどうかを確認する問題であり、負の周期があるかどうかを確認することである.すなわち、サイクルの時間が長ければ長いほど、幹線の値は小さくなる.

に近づく

せいげんじょうけん

しかし問題は、時間が後退した状況を判断する際、白俊がどこから出発したのか明確ではないということだ.つまり、始点が1番に固定されているのではなく、すべての場所から出発することができます.そのため、すべての場所でベルマンフォードを迂回しなければなりません.しかし、ベルマンフォードは1つの点で回転するだけで、O(VE)O(Vcdote)O(VE)O(VE)(V2)O(V\cdote)O(V\E)E)E)を必要とする.O(n 3)O(n^3)O(n 3)O(n 3)Oに近い(頂点が誰にも接続されていないと仮定すると、幹線の数は常に頂点の数より大きい)時間がタイムアウトする.別の方法が必要に見える.まず最短距離は聞かず、マイナスサイクルかどうかを判断すればいいので、最短距離は気を使わなくてもいいはずです.

解決する

通常、ベルマンフォードを迂回すると、最短距離配列が宣言され、開始点が0に設定され、残りの値は-1 또는 NULLになります.その理由は、2つの頂点の1つに1つの直線上でアクセスしてこそ、累積した幹線値を計算できるため、複数の曲線に似ています.ただし、コンストレイントで説明したように、すべての頂点数でベルマンフォードを回転させると、タイムアウトが発生する可能性があります.タイムアウトを回避するには、すべての頂点から同時に開始する必要があるため、最短距離配列をすべてゼロにリセットします.これにより、任意の幹線を使用して幹線値を計算でき、時間を短縮できます.

アルゴリズム#アルゴリズム#

分かりやすいように、例入力1の2つのケースを例に挙げましょう.

Case 1[負周期X]

入力(虫穴は一方向、ルートは双方向)

始点終点幹線値122211314432312311-3

Graph

最短距離アレイを0にリセットし、幹線数+1の長さにします.

[0, 0, 0, 0]

ベルマンフォードはすべての幹線を정점 갯수回巡回した.最後の2サイクルは、最短距離(負のサイクル)をリフレッシュするかどうかを決定します.まずは全幹線を1回(残り2回)

回って
[0,-3,0,0]

の最短距離はすべてゼロであるため、一部の幹線値が負でない限り、最短距離のデータはリフレッシュされません.3番->1番までの幹線値は-3なので、1番頂点までの最短距離は-3に更新されます.

は再び同じように幹線を巡視した.(残り1回)

[0,-3,-1,0]

1号の-3から2号までの距離値を-3 + 2 = -1と求めた.でも前の2番は最短距離が0だったので-1に更新

最後の巡視幹線.今回の更新が最短距離であれば、マイナスサイクルとみなされます.(残り0回)[0,-3,-1,0]

は最短距離を更新していないため、負周期のパターンは存在しないと判定される.

Case 2[負周期O]

入力(虫穴は一方向、ルートは双方向)

始点終点幹線値12321234332431-8

Graph

Case 1と同様にアレイを初期化します.

[0, 0, 0, 0]

幹線を巡視する.(残り2回)、3->1の幹線値は-8なので、1番頂点の最短距離は-8に更新されます.

[0, -8, 0, 0]

本線(残り1回)を再巡視し、1時から2に移動した値は3であるが、1回の最短距離は-8であるため、3 - 8 = -5、すなわち2回の最短距離は-5となる.同様に、3番幹線値は4ですが、3番前の頂点-2の最短距離は-5なので、-5 + 4 = -1すなわち-1に更新されます.最後に、最初の3番目の頂点が-1であるため、1番の頂点も-8 + -1 = -9、すなわち-9に更新される.

[0, -9, -5, -1]

ご覧のように、すべての頂点が更新されました.最短距離が負の場合は、次の巡視、以降の巡視、幹線値が負の場合は更新を続行します.ただし既に3->1の値は-8なので、最終的にはすべて更新される可能性があります.ベルマンフォードは、このような負の周期の無限の更新を阻止するために、幹線巡視を정점 갯수回に制限した.

最後のツアー.今はマイナスサイクルを判定する番だ.(残り0回)、1->2の幹線値は3であるが、1回の最短距離は-9であるため、この値は-6と計算される.ただし2の最短距離は-5なので-6に更新そして、2->3をチェックすると、幹線値が4番、2番に更新される最短距離は-6となるため、-6を計算すると-2となるが、3番の最短距離値は-1となるため、同様に3番が更新される.最後に、1−>3では、幹線値は−8であるが、最短距離を−2に3回更新するので、計算すると、−1の最短距離ではなく−10に更新される.結果は予想通り全て更新しましたループ数を制限せずに他の条件でループを回転させると、最短距離は更新され続けます.これを負の周期と呼ぶ.しかし,回数制限を設け,更新されたことを知っているため,負周期と判定した.

[0, -10, -6, -2]

コード#コード#

プライマリコード

for _ in range(T):
    V, E, WE = map(int, input()[:-1].split())

    EDGES = []
    R = [0] * (V + 1)
    for _ in range(E):
        # 일반 노선 갖고오기
        u, v, w = map(int, input()[:-1].split())
        EDGES.append((u, v, w))
        EDGES.append((v, u, w))
    for _ in range(WE):
        # 웜홀
        u, v, w = map(int, input()[:-1].split())
        EDGES.append((u, v, -w))
    
    if process(V, E*2+WE, EDGES, R):
        # 시간이 줄어듦
        result.append("YES")
    else:
        result.append("NO")
print('\n'.join(result))

すべてを同時に計算するために、幹線アレイはINFまたはNoneに初期化され、0ではない.

R = [0] * (V + 1)

アルゴリズムコード

def process(V, E, edges, weights):
    def bfs():
        for i in range(V):
            for j in range(E):
                u, v, w = edges[j]
                if weights[v] > weights[u] + w:
                    weights[v] = weights[u] + w
                    if i == V - 1:
                        return True
        return False
    is_cycle = bfs()
    if is_cycle:
        return True
    else:
        return False

頂点数V、幹線数E、頂点および幹線数edges、weightsをパラメータ値として受け入れ、負の周期を返します.
すべての幹線は정점 갯수回巡回した.

for i in range(V):
    for j in range(E):

始点u、終点v、および幹線値wは、幹線図(またはリスト)から取得される.

u, v, w = edges[j]

if weights[v] > weights[u] + w:
    weights[v] = weights[u] + w
    if i == V - 1:
        return True

最短距離uと最短距離vの幹線値wを加算すると、従来のvの最短距離よりも更新が小さくなる.しかし、最後のツアーで更新を行うと、負のサイクルであるため、Trueが返されます.そうでなければ、for文から終了すると、Falseが返されます.

ポスト

私がこの問題をしたとき、私はベルマンフォードアルゴリズムを勉強したばかりで、タイムマシンの問題をして、それから私はこの問題をしました.これはベルマンフォードアルゴリズムの原理をもっと詳しく学ぶ機会です.特に、負の周期の原理がよく分からないことがよく分かりました.もしあなたが私と同じようにベルマンフォードアルゴリズムを勉強しているなら、私はあなたにこの問題をお勧めします.