ループと負のエッジを持つ無向グラフで BFS (通過した最小頂点を使用) を使用して、O(log n) 時間でソースから宛先を見つけることは可能ですか?
例: N 個の頂点と N 個の辺を持つ単純な連結グラフ G が与えられます (単純なグラフとは、ループがなく、2 つの異なる頂点間に辺が 1 つしかない無向グラフです)。グラフ G が正確に 1 つのサイクルを含むことは明らかであり、このサイクルの長さは奇数であると仮定できます (このサイクルには奇数の頂点があります)。頂点には 1 から N までの番号が付けられます。各エッジには、対応する整数の重みが割り当てられます。あなたの使命は、2 種類のクエリを刺激することです: fuv で表されるクエリを更新します: 最短経路上のエッジのすべての重みの符号を変更します (この問題の最短経路の定義は後で確認できます) 頂点 u から頂点へv. ? で表される検索クエリ uv: 頂点 u から頂点 v への最短経路上で、重みの合計が最大になるように、連続したエッジの (おそらく空の) セットを見つけます。つまり、u から v への最短経路を a_1、a_2、...、a_k (a_1 = u および a_k = v) として定義しましょう。i <= j で、パス a_i、a_(i + 1)、...、a_j のエッジの重みの合計ができるだけ大きくなるような a_i と a_j を見つける必要があります。その合計を見つけるだけです。2 つの頂点 u と v の間の最短経路は、それらを最小数の頂点で結ぶ経路です。この問題では、G の頂点の任意のペア間に最短経路が 1 つしかないことは明らかです。a_(i + 1), ..., a_j はできるだけ大きくします。その合計を見つけるだけです。2 つの頂点 u と v の間の最短経路は、それらを最小数の頂点で結ぶ経路です。この問題では、G の頂点の任意のペア間に最短経路が 1 つしかないことは明らかです。a_(i + 1), ..., a_j はできるだけ大きくします。その合計を見つけるだけです。2 つの頂点 u と v の間の最短経路は、それらを最小数の頂点で結ぶ経路です。この問題では、G の頂点の任意のペア間に最短経路が 1 つしかないことは明らかです。