Editorial for Haskell

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

A positive-weight cycle exists if and only if the graph with every edge weight negated contains a negative-weight cycle. Detect that negative cycle with Bellman-Ford.

Negate every edge weight, then initialize $dist[v] = 0$ ~dist[v] = 0~ for all vertices (so a negative cycle anywhere is visible, not only cycles reachable from a fixed source). Relax all edges $n - 1$ ~n - 1~ times. If any edge can still be relaxed afterward, a negative cycle exists in the negated graph, which means a positive cycle exists in the original graph.

The time complexity is $O(nm)$ ~O(nm)~.

Solution (C++)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> from, to, weight;
  from.reserve(m);
  to.reserve(m);
  weight.reserve(m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    // Negate weights: a positive cycle becomes a negative cycle.
    from.push_back(a);
    to.push_back(b);
    weight.push_back(-c);
  }

  // Initialize all distances to 0 so any negative cycle in the graph is detectable.
  vector<long long> dist(n + 1, 0);
  for (int iter = 0; iter < n - 1; iter++) {
    bool updated = false;
    for (int i = 0; i < m; i++) {
      if (dist[to[i]] > dist[from[i]] + weight[i]) {
        dist[to[i]] = dist[from[i]] + weight[i];
        updated = true;
      }
    }
    if (!updated) {
      break;
    }
  }

  for (int i = 0; i < m; i++) {
    if (dist[to[i]] > dist[from[i]] + weight[i]) {
      cout << "YES\n";
      return 0;
    }
  }
  cout << "NO\n";
  return 0;
}

Comments

There are no comments at the moment.