Mon approche est-elle correcte?

Question

Je suis aux prises avec le problème suivant:

donné un graphe orienté avec 3 < = N = 1000 < sommets et 3 < = M < = 1000000 bords vous pouvez choisir un cycle simple de ce graphique et marcher it.While vous marchez le cycle à chaque bord vous êtes posé une question si vous répondez correctement votre argent est doublé autrement il est réduit de moitié.

Disons que vous avez dollars D et la chance vous répondez correctement à une question à un E_I de bord est p_i, l'argent devrait avoir après avoir répondu à cette question est:

2 * D p_i + de 1/2 (D (1-p_i)) = D (1/2 + 3 * p_i/2)

Cherchez s'il y a un cycle simple dans le graphique donné que vous pouvez marcher et l'argent que vous aurez après avoir marché c'est plus que l'argent que vous avez commencé avec. Mon approche consiste à utiliser l'algorithme de Johnson pour trouver tous les cycles simples et ensuite vérifier s'il y a un cycle pour lequel l'argent attendu est supérieur à celui avec lequel vous commencez mais je continue à obtenir des temps morts. Est-ce que je manque quelque chose? Y a-t-il une observation à faire ou devrais-je juste essayer d'optimiser mon code plus?

Answer 1

L'astuce dans ce problème est de réduire cela à la détection de cycle négatif.

Si vous commencez avec x somme d'argent d'un sommet et aller autour d'un cycle e_1,e_2,…e_k et revenez, vous finirez avec x*f_1*f_2*…f_k où f_i=(1/2+3*p(e_i)/2). Ce que vous voulez, c'est f_1*f_2*…f_k > 1. Mais c'est la même chose que d'avoir ln(f_1) + ln(f_2) … ln(f_k) > 0. Par conséquent, créez un graphique avec des poids de bord de -ln(f_k). Le problème se réduit alors à la détection de cycle négatif, ce qui peut être fait en utilisant un algorithme comme Bellman-Ford.