私のアプローチは正しいですか？私は、次のような問題に苦しんでいます

Question

：3 < = N < = 1000頂点とあなたがこのグラフの簡単なサイクルを選択し、it.Whileを歩くことができる3 < = M < = 1000000のエッジを持つ有向グラフを考える

あなたはあなたのお金が正しく倍増されればあなたは質問されている各エッジでサイクルを歩いています。

のは、あなたがDのドルを持っていると言うと、あなたがエッジe_iで正しく質問に答える機会がP_Iで、その質問に答えるの後が期待お金がある：

2 * D P_I + 1/2 （D（1-p_i））= D（1/2 + 3 * p_i/2）

歩くことができるグラフと歩いた後の予想される金額それはあなたが始まったお金よりもはるかです。

私のアプローチは、すべての単純なサイクルを見つけて、予想される金額が最初のものより多いサイクルがあるかどうかを確認することですが、タイムアウトが発生します。何か不足していますか？私がしなければならないことがありますか、私はもっとコードを最適化しようとするべきですか？

Answer 1

この問題のトリックは、これを負のサイクル検出に減らすことです。

あなたは頂点からお金のx量で開始し、サイクルe_1,e_2,…e_kの周りに行くと戻って取得する場合は、x*f_1*f_2*…f_kf_i=(1/2+3*p(e_i)/2)になってしまいます。あなたが欲しいのはf_1*f_2*…f_k > 1です。しかしこれはln(f_1) + ln(f_2) … ln(f_k) > 0と同じです。

エッジ重みが-ln(f_k)のグラフを作成します。この問題は、Bellman-Fordのようなアルゴリズムを使用して行うことができる負のサイクル検出に還元されます。