Жингийн нийлбэр нь сөрөг cycle байгаа эсэхийг шалгаж, байвал тэр cycle-ыг хэвлэх арга.

Advanced & LegendХугацаа: O(n · m)Санах ой: O(n + m)

Эхлээд жижиг бодлого

3 node, edge нь 1 2 1, 2 3 -3, 3 2 1. 2 → 3 → 2 cycle-ын жингийн нийлбэр -3 + 1 = -2, сөрөг. Тэгэхээр хариу YES.

Код cycle-ыг 3 2 3 гэж хэвлэнэ. Харин 3 2 4 гэж өөрчилбөл нийлбэр нь -3 + 4 = 1 болж, хариу NO.

Энгийн аргаас санаа руу

Энгийн арга бол бүх cycle-ыг тоочиж нийлбэрийг нь шалгах. Cycle-ын тоо экспоненциал өснө.

Bellman–Ford-ын санаа: сөрөг cycle байхгүй бол бүх edge-ийг n - 1 удаа шалгахад зай тогтворжино. Тэгэхээр n дэх давталтад зай дахиад багасвал сөрөг cycle бий. Бүх d-г 0-ээс эхлүүлбэл node бүрээс зэрэг эхэлсэнтэй адил тул graph-ын хаана ч байгаа cycle олдоно. p заагч нь cycle-ыг сэргээхэд хэрэгтэй.

Нэр томьёо ба тэмдэглэгээ

negative cycle
Edge-үүдийн жингийн нийлбэр нь сөрөг cycle.
d[v]
Одоогоор олдсон хамгийн бага зай. Бүгд 0-ээс эхэлнэ.
p[v]
d[v]-г хамгийн сүүлд багасгасан edge-ийн эхлэл node.
x
Давталт бүрт хамгийн сүүлд зай нь багассан node. n дэх давталтын дараа 0 биш бол cycle бий.
relax
d[u] + w < d[v] бол d[v] = d[u] + w болгох алхам.
342-4121d=02d=03d=04d=05d=0
p[1..5] = 0 0 0 0 0

Жингийн нийлбэр нь сөрөг cycle (negative cycle) байна уу? Эхэндээ бүх d = 0, өөрөөр хэлбэл node бүр өөрөө эхлэл. Ногоон edge нь p[v]: v зайгаа хэнээс авсныг заана.

Алхам 1 / 29
Хурд
  • Шалгаж буй edge / cycle-ын edge
  • Зай нь сая багассан
  • p заагч (хаанаас ирсэн)
  • Cycle доторх node x
  • Олдсон сөрөг cycle
Слайд 1 / 6

Сөрөг cycle

Cycle-ын жингийн нийлбэр сөрөг бол түүгээр тойрох тусам зам улам богиносно. Ийм cycle байна уу, байвал аль нь вэ гэдгийг олъё.

negative-cycle.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, u[5005], v[5005], w[5005], p[2505];
long long d[2505];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i];
int x = 0;
for (int r = 1; r <= n; r++) {
x = 0;
for (int i = 0; i < m; i++) {
if (d[u[i]] + w[i] < d[v[i]]) {
d[v[i]] = d[u[i]] + w[i];
p[v[i]] = u[i];
x = v[i];
}
}
}
if (x == 0) {
cout << "NO\n";
return 0;
}
for (int i = 1; i <= n; i++) x = p[x];
vector<int> cyc = {x};
for (int y = p[x]; y != x; y = p[y]) {
cyc.push_back(y);
}
cyc.push_back(x);
reverse(cyc.begin(), cyc.end());
cout << "YES\n";
for (int y : cyc) cout << y << ' ';
return 0;
}

Юунд хэрэгтэй вэ?

Сөрөг cycle-тай graph-т «хамгийн богино зам» гэж байдаггүй: тойрох тусам зам богиносно. Валютын арбитраж, хязгааргүй ашиг олох зэрэг бодлогод ийм cycle-ыг олох хэрэгтэй.

Яаж ажилладаг вэ?

1. d бүгд 0. Энэ нь node бүрээс зэрэг эхэлсэнтэй адил. 2. n удаа давтана: давталт бүрт бүх edge-ээр d[u] + w < d[v] бол d[v] = d[u] + w, p[v] = u, x = v. 3. Сүүлийн давталтад ч зай багассан бол (x ≠ 0) сөрөг cycle бий, үгүй бол NO. 4. x = p[x] үйлдлийг n удаа давтана. Ингэхэд x заавал cycle дотор орно. 5. x-ээс p заагчийг дагаж x дээр буцаж иртэл цуглуулаад урвуулна. Оролт: n m, дараа нь m мөрөнд «u v w» (u → v, жин w). Гаралт: YES ба cycle, эсвэл NO.

Яагаад зөв, хэр хурдан бэ?

Сөрөг cycle байхгүй бол хамгийн богино path хамгийн ихдээ n - 1 edge-тэй тул n - 1 давталтын дараа ямар ч зай багасахгүй. Сөрөг cycle байвал түүнийг тойрох бүрт зай багасах тул n дэх давталтад заавал relax болно. x-ээс p-гээр n удаа ухрахад p-ийн гинж cycle рүү заавал орно: гинж n node-оос урт тул давтагдана. Тэндээс эхэлж эргэж иртэл цуглуулбал cycle гарна.

n давталт, давталт бүрт m edge. Хугацаа O(n · m). n = 2500, m = 5000 бол 12.5 сая алхам.

Түгээмэл алдаа

  • x-ийг шууд cycle-ын node гэж үзэх. x нь cycle-аас "урсаж" гарсан node байж болно. Эхлээд n удаа ухар.
  • d-г INF-ээр эхлүүлэх. Тэгвэл node 1-ээс хүрэхгүй cycle олдохгүй. Энэ код бүгдийг 0-ээс эхлүүлдэг.
  • d-г int-ээр хадгалах. Олон удаа сөрөг жин нэмэгдэхэд int хэтэрч болно, код long long ашигладаг.
  • Давталт бүрийн эхэнд x = 0 болгохоо мартах. Тэгвэл өмнөх давталтын x үлдэж, cycle байхгүй ч YES гэнэ.

Хязгаарын тохиолдол

  • Бүх жин эерэг: эхний давталтаас эхлэн нэг ч relax болохгүй, хариу NO.
  • Graph-т cycle байгаа ч нийлбэр нь 0 эсвэл эерэг: хариу NO.
  • Сөрөг cycle node 1-тэй холбоогүй: d бүгд 0 тул мөн олдоно.

Өөрийгөө шалга

  1. 1 2 2, 2 3 2, 3 1 -5 graph-т код юу хэвлэх вэ?

    Хариу харах

    YES, дараа нь 1 2 3 1. Нийлбэр 2 + 2 - 5 = -1.

  2. Яагаад n - 1 биш n давталт хийдэг вэ?

    Хариу харах

    Эхний n - 1 давталт зайг тогтворжуулна. n дэх давталтад зай багасах эсэх нь сөрөг cycle байгаа эсэхийг хэлдэг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Animation-ы жишээнд (1 2 3, 1 3 4, 2 3 2, 3 4 -4, 4 2 1, 4 5 2) ямар cycle олдох вэ?

    Hint харах

    Сөрөг жинтэй edge-ийг агуулсан cycle-ыг хай.

    Хариу ба тайлбар

    2 → 3 → 4 → 2, нийлбэр 2 - 4 + 1 = -1. Код 3 4 2 3 гэж хэвлэнэ.

  2. 2.Валютын ханш r[i][j] (1 нэгж i валютаар хэдэн j авах) өгөгдсөн. Солилцсоор ашиг олж болох эсэхийг шийд.

    Hint харах

    Үржвэр 1-ээс их байх cycle-ыг логарифм аваад нийлбэр болго.

    Хариу ба тайлбар

    Edge i → j бүрийн жинг -log(r[i][j]) гэж аваад энэ кодыг double-аар ажиллуулна. Сөрөг cycle байвал ашигтай солилцоо бий.

  3. 3.Зөвхөн node 1-ээс хүрч болох сөрөг cycle-ыг ол.

    Hint харах

    d-г хэрхэн эхлүүлэхийг өөрчил.

    Хариу ба тайлбар

    d[1] = 0, бусдыг INF болгоно. Relax хийхийн өмнө d[u] != INF-ийг шалгана. Үлдсэн код ижил.

Жишээ

Оролт

5 6
1 2 3
1 3 4
2 3 2
3 4 -4
4 2 1
4 5 2

Гаралт

YES
3 4 2 3