Please help me with this problem: Given an undirected weighted graph have n vertices and m edges (n <= 1000, m <= 10000). How to check if there exists a simple cycle have total weight >= 0. Thanks for your help.

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 144 |

Please help me with this problem: Given an undirected weighted graph have n vertices and m edges (n <= 1000, m <= 10000). How to check if there exists a simple cycle have total weight >= 0. Thanks for your help.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 08:44:22 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You can multiply each edge weight by $$$-1$$$. Then use Bellman Ford's algorithm to find a negative cycle which iirc works in $$$O(n^2 + n \cdot m)$$$.

But as far as I know, it can only be used for directed graph. When use it in undirected graph, this algorithm can go on a loop in a negative weighted edge (cycle of length 2) but it not simple cycle.

Not sure. There's another approach you can try. It has an $$$O(m^2)$$$ complexity so not sure if it will pass. For eaxh edge from node $$$a$$$ to node $$$b$$$ with weight $$$w$$$, "remove" that edge, then find the shortest distance between $$$a$$$ and $$$b$$$ (assuming there is indeed a path between these after removing the edge). Let the distance found be $$$p$$$. You have a cycle with weight $$$p+w$$$.

But how can we find the shortest distance between a and b ? It still can go on a loop in a negative weighted edge.

Can someone help me please. I still can't solve this problem.

Sorry I forgot to reply back. You can use modified Bellman Ford's: keep track of the node used to relax the distance for every node, this way you can avoid 2 node cycles.

problem link??

I think you can use Bellman Ford's algorithm but with vertices {vertex, last edge}, and then you update distance only if new edge is not equal to the last edge used. I think it will still be O(m^2) because every edge creates only 2 new vertices.