En teoría de grafos, un ciclo negtaivo es aquell donde la suma de los pesos de las aristas es menor que cero. Para el caso de productos, se puede aplicar una transformación logarítmica.

Un ciclo positivo se refiere a un camino más largo en un grafo con pesos.

Consideremos un problema donde se intercambian a unidades de b por wc unidades de d, buscando el valor máximo de w en el intervalo [0,1] que maximice la cantidad resultante. Esto se resuelve combinando búsqueda binaria con la detección de ciclos negativos usando el algoritmo SPFA.

La idea clave es transformar los pesos de las aristas usando logaritmos: para cada intercambio, el peso se calcula como -log(c/a), y se añade un término de búsqueda binaria mid. Si existe un ciclo negativo en el grafo transformado, entonces mid es factible.

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef pair<int, ld> edge;

const int MAX_NODES = 1010;

int num_nodes, num_edges;
vector<edge> adjacency[MAX_NODES];
ld distances[MAX_NODES];
int update_counts[MAX_NODES];
bool in_queue[MAX_NODES];

bool validate(ld candidate) {
    ld adjusted = -log(candidate);
    fill(distances, distances + num_nodes + 1, 0.0);
    fill(in_queue, in_queue + num_nodes + 1, false);
    fill(update_counts, update_counts + num_nodes + 1, 0);

    queue<int> processing_queue;
    for (int i = 1; i <= num_nodes; ++i) {
        processing_queue.push(i);
    }

    while (!processing_queue.empty()) {
        int current = processing_queue.front();
        processing_queue.pop();
        in_queue[current] = false;

        for (auto &next_edge : adjacency[current]) {
            int neighbor = next_edge.first;
            ld weight = next_edge.second;
            if (distances[neighbor] > distances[current] + weight + adjusted) {
                distances[neighbor] = distances[current] + weight + adjusted;
                update_counts[neighbor] = update_counts[current] + 1;
                if (update_counts[neighbor] >= num_nodes) return false;
                if (!in_queue[neighbor]) {
                    processing_queue.push(neighbor);
                    in_queue[neighbor] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    scanf("%d %d", &num_nodes, &num_edges);

    while (num_edges--) {
        int from, to, numerator, denominator;
        scanf("%d %d %d %d", &from, &to, &numerator, &denominator);
        adjacency[to].push_back({denominator, -log(static_cast<ld>(numerator) / from)});
    }

    ld low = 0.0, high = 1.0;
    while (high - low > 1e-10) {
        ld mid = (low + high) / 2;
        if (validate(mid)) low = mid;
        else high = mid;
    }
    printf("%.10Lf\n", low);
    return 0;
}

Otro ejemplo común es el problema de los agujeros de gusano, donde se determina si existe un ciclo negativo. Se modela con aristas bidireccionales de peso positivo y aristas unidireccionales de peso negativo.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 510, M = 5201;

int head[N], edge_to[M], edge_weight[M], next_edge[M], idx;
bool visited[N];
int counter[N];
int distance[N];

void add_edge(int u, int v, int w) {
    edge_to[idx] = v;
    edge_weight[idx] = w;
    next_edge[idx] = head[u];
    head[u] = idx++;
}

bool spfa(int n) {
    queue<int> q;
    memset(visited, false, sizeof(visited));
    memset(distance, 0, sizeof(distance));
    memset(counter, 0, sizeof(counter));

    for (int i = 1; i <= n; ++i) {
        q.push(i);
        visited[i] = true;
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        visited[u] = false;

        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = edge_to[i];
            if (distance[v] > distance[u] + edge_weight[i]) {
                distance[v] = distance[u] + edge_weight[i];
                counter[v] = counter[u] + 1;
                if (counter[v] >= n) return true;
                if (!visited[v]) {
                    q.push(v);
                    visited[v] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, s;
        cin >> n >> m >> s;
        memset(head, -1, sizeof(head));
        idx = 0;

        for (int i = 0; i < m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        for (int i = 0; i < s; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, -w);
        }

        cout << (spfa(n) ? "YES" : "NO") << endl;
    }
    return 0;
}

Para problemas de programación fraccionaria 01 con ciclos, se puede transformar pesos de nodos a aristas y usar SPFA para detecatr ciclos positivos. Esto involucra búsqueda binaria sobre el valor objetivo.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010, M = 5010;

int node_value[N];
int head[N], edge_to[M], edge_cost[M], next_edge[M], idx;
double dist[N];
bool in_queue[N];
int update_cnt[N];
int q[N];

void add_edge(int u, int v, int w) {
    edge_to[idx] = v;
    edge_cost[idx] = w;
    next_edge[idx] = head[u];
    head[u] = idx++;
}

bool check(double mid, int n) {
    memset(dist, 0, sizeof(dist));
    memset(in_queue, 0, sizeof(in_queue));
    memset(update_cnt, 0, sizeof(update_cnt));

    int front = 0, rear = 0;
    for (int i = 1; i <= n; ++i) {
        q[rear++] = i;
        in_queue[i] = true;
    }

    while (front != rear) {
        int u = q[front++];
        if (front == N) front = 0;
        in_queue[u] = false;

        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = edge_to[i];
            double new_dist = dist[u] + node_value[u] - mid * edge_cost[i];
            if (dist[v] < new_dist) {
                dist[v] = new_dist;
                update_cnt[v] = update_cnt[u] + 1;
                if (update_cnt[v] >= n) return true;
                if (!in_queue[v]) {
                    q[rear++] = v;
                    if (rear == N) rear = 0;
                    in_queue[v] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> node_value[i];

    memset(head, -1, sizeof(head));
    idx = 0;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    double low = 0.0, high = 1e6;
    while (high - low > 1e-4) {
        double mid = (low + high) / 2;
        if (check(mid, n)) low = mid;
        else high = mid;
    }
    printf("%.2lf\n", low);
    return 0;
}

Un truco práctico en la detección de ciclos es limitar las actualizaciones: si algún nodo se actualiza más de 5N veces, se considera probable la existencia de un ciclo. Sin embargo, es más preciso verificar si existe al menos un ciclo que satisfaga la condición.