# TDA | Practica 5 ejercicio 7 ## Consigna 7. Para organizar el trafico, la ciudad de Ciclos Positivos ha decidido implementar las cabinas de peaje inverso. La idea de estas cabinas es incentivar la circulación de vehículos por caminos alternativos, estableciendo un monto que se le paga a le conductore de un vehículo cuando pasa por la cabina. Estas cabinas inversas se suman a las cabinas regulares, donde le conductore paga por pasar por la cabina. La ciudad sabe que estas nuevas cabinas pueden dar lugar al negocio del “ciclo puré", que consiste en transitar $e\textit{ternamente por la ciudad a fı n de obtener una ganancia}$ que tienda a infinito. Para evitar esta situación, que genera costos y tráfico adicional, lo cual será aprovechado para desgastar a la administración ante la opinion pública, la ciudad quiere evaluar distintas alternativas antes de llevar las cabinas inversas a la práctica. # - $a.$ Modelar el problema de determinar si la ciudad permite el negocio del ciclo puré cuando el costo de transitar por cada cabina $i$ de peaje es $c_i(c_i<0$ si la cabina es inversa) y el costo que cuesta viajar de forma directa de cada cabina $i$ a cada cabina $j$ es $c_ij>0.$ - $b.$ Dar un algoritmo para resolver el problema del inciso anterior, indicando su complejidadtemporal. # - El sistema arrojó que ninguna de las configuraciones deseadas para desincentivar el tráfico evita el negocio de los ciclos puré. Desafortunadamente, el plan se filtró a la prensa y comenzaron las peleas mediáticas. A fn de obtener cierto rédito, desde el departamento de marketing sugieren transformar la idea de cabinas inversas en cabinas mixtas. Cuando un vehículo pasa por una cabina mixta, se le paga a le conductore si se le cobró a le conductore en la cabina anterior; caso contrario, le conductore paga. Obviamente, desde marketing sugieren que se le pague a le conductore cuando la cabina mixta sea la primera cabina recorrida para bajar los malos humores. $c.$ Modelar el problema de determinar si la ciudad permite el negocio de los ciclos puré cuando se aplica la nueva confguración para las cabinas. Además de la información utilizada para el problema original, ahora se conoce cuáles cabinas son mixtas: notar que el monto de cobro es $c_i$ y el monto de pago es $-c_i$ para la cabina mixta $i$ (con $c_i>0).$ # ## Resolución ### a) - Las aristas "inversas" tienen costo negativo, el ciclo puré refiere a un ciclo con unicamente aristas negativas del que nunca podría salir. - Hay que ver si $i$ es $C_i$ negativa. - El costo de transitar por cada $i$ es $C_i$. - $C_i < 0$ si la cabina es inversa. - Y el costo de viajar de forma directa de una cabina $i$ a cada cabina $j$ es $C_{ij}>0$ (costo de transitar adirectamente desde $i$ a $j$, este costo puede ser negativo). - **Empezá a leer desde acá:** - Entonces tenemos que: - Cabina = Vértice - Peaje = Arista - En un digrafo pesado con aristas positivas y negativas - No tenemos que permitir ciclos negativos. ### b) - Bellman-Ford detecta y sabe manejar ciclos negativos - iniciar $\to$ relax $\to$ chequear ciclos - Complejidad asintotica temporal: $O(V \times E)$ ### c) - Se le paga al conductor si se le cobró en la anterior, si no, paga el conductor. - Puede haber dos estados: - Cobrado: El conductor fue cobrado en la cabina anterior - Pagado: el conductor fue pagado en la cabina anterior. - Entonces cada cabina: $i_p$ ó $i_c$ - Crear aristas con condiciones - Cabina normal - Cobra: Crear arista $j_{p \oplus c} \to i_c$ - Paga: $j_{p \oplus c} \to i_p$ - Cabina mixta - $j_c \to i_p$ - $j_p \to i_c$