Node 1-ээс эхэлж, tree-гээс гарах хамгийн бага жинтэй edge-ийг үргэлж авсаар бүх node-ыг холбох арга.

Advanced & LegendХугацаа: O(m log m)Санах ой: O(n + m)
HackerRank дээр бодох

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

3 node, edge нь 1 2 3, 2 3 1, 1 3 2. Бүх node-ыг холбох хамгийн бага нийт жин хэд вэ?

Node 1-ээс эхэлнэ. Node 1-ээс гарах edge-үүдээс хамгийн бага нь 1 3 2 тул node 3-ыг авна. Одоо tree {1, 3}-аас гарах edge-үүд нь 1 2 3, 3 2 1. Хамгийн бага нь 3 2 1. Нийт жин 2 + 1 = 3.

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

Энгийн арга бол n - 1 edge-ийн бүх сонголтыг шалгаж, холбоотой эсэхийг нь шалгах. Хувилбар нь асар олон.

Гол санаа (Greedy): нэг node-оос эхэлж tree-гээ ургуулна. Алхам бүрт tree-гийн дотор ба гадна талыг холбосон edge-үүдээс хамгийн бага жинтэйг нь авна. Энэ edge-үүдийг priority_queue-д хадгалбал хамгийн багыг нь хурдан олно.

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

MST
Minimum Spanning Tree: бүх node-ыг холбосон, нийт жин нь хамгийн бага tree.
pq
(жин, node) хосын priority_queue. greater ашигласан тул хамгийн бага жинтэй нь дээр байна.
used[u]
Node u tree-д орсон эсэх.
total, cnt
Tree-гийн нийт жин ба tree-д орсон node-ын тоо.
412536724123456
total = 0cnt = 0
pq — (жин, node)
хоосон

Бүх node-ыг холбодог, нийт жин нь хамгийн бага tree-г олъё. Үүнийг MST гэнэ. Node 1-ээс эхэлж tree-гээ ургуулна: tree-гээс гарах хамгийн бага жинтэй edge-ийг үргэлж авна.

Алхам 1 / 25
Хурд
  • Одоогийн node / edge
  • Сая tree-д орсон
  • pq-д хүлээж буй edge
  • Tree-д орсон
  • Бэлэн MST
Слайд 1 / 7

Tree-гээ ургуулъя

Бүх хотыг хамгийн бага зардлаар холбоё. Prim node 1-ээс эхэлж, tree-гээ нэг нэг node-оор ургуулна.

prim.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
long long total;
vector<pair<int, int>> g[100005];
bool used[100005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
pq.push({0, 1});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (used[u]) continue;
used[u] = true;
total += w;
cnt++;
for (auto [v, c] : g[u]) if (!used[v]) pq.push({c, v});
}
cout << (cnt == n ? total : -1) << '\n';
return 0;
}

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

Бүх node-ыг нийт жин нь хамгийн бага tree-гээр (MST) холбоно. Kruskal ч ижил хариу өгнө. Edge олонтой graph-т Prim ихэвчлэн илүү тохиромжтой.

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

1. (0, 1) хосыг priority_queue-д хийнэ. 2. pq-гээс хамгийн бага жинтэй (w, u) хосыг гаргана. 3. Node u аль хэдийн tree-д байвал алгасна. 4. Үгүй бол node u tree-д орж, total += w, cnt++. 5. Tree-д ороогүй хөрш v бүрт (c, v) хосыг pq-д нэмнэ. Энд c нь u–v edge-ийн жин. 6. pq хоосроход cnt = n бол хариу total, үгүй бол -1. Оролт: n m, дараа нь m мөрөнд «u v w» (чиглэлгүй edge).

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

Tree-гийн дотор ба гадна талыг холбосон хамгийн бага жинтэй edge заавал ямар нэг MST-д ордог. Хэрэв MST-д ороогүй бол түүнийг нэмээд үүссэн cycle-аас илүү хүнд edge-ийг хасахад нийт жин багасна. Иймээс алхам бүрийн сонголт аюулгүй.

Edge бүр хамгийн ихдээ хоёр удаа pq-д орно. Хугацаа O(m log m). n = 100 000, m = 200 000 бол хэдэн сая үйлдэл.

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

  • pq-гээс гарсан node аль хэдийн tree-д байгаа эсэхийг шалгахгүй байх. Тэгвэл нэг node-ыг хоёр удаа нэмж, total буруу гарна.
  • total-ыг int-ээр хадгалах. 100 000 edge, жин нь 10⁹ хүртэл бол нийлбэр int-ээс хэтэрнэ. Код long long ашигладаг.
  • Graph холбоотой эсэхийг шалгахгүй байх. cnt < n бол MST байхгүй, -1 хэвлэнэ.

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

  • n = 1: (0, 1)-ийг аваад cnt = 1 = n, хариу 0.
  • Graph хоёр хэсэгтэй: node 1-ийн хэсэг л tree-д орно, хариу -1.
  • Ижил жинтэй edge-үүд: MST олон байж болох ч нийт жин нь ижил.

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

  1. 4 node, edge нь 1 2 1, 3 4 1. Код юу хэвлэх вэ?

    Хариу харах

    -1. Node 3, 4-т node 1-ээс хүрэхгүй тул cnt = 2 < 4.

  2. Prim ба Kruskal ижил graph дээр ижил нийт жин өгөх үү?

    Хариу харах

    Тийм. MST олон байж болох ч бүгд ижил нийт жинтэй.

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

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

  1. 1.4 node, edge нь 1 2 1, 2 3 2, 3 4 3, 4 1 4, 1 3 5. Prim ямар edge-үүдийг ямар дарааллаар авах вэ?

    Hint харах

    Алхам бүрт pq-д ямар хос байгааг бич.

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

    1 2 1, дараа нь 2 3 2, дараа нь 3 4 3. Нийт жин 6.

  2. 2.MST-д орсон edge-үүдийг хэвлэдэг болго.

    Hint харах

    pq-д (жин, node)-оос гадна хаанаас ирснийг хадгал.

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

    pq-д {c, {v, u}} хэлбэрээр хийнэ. Node v-г tree-д оруулах үед u v c edge-ийг жагсаалтад нэмнэ. Эхний (0, 1) хосыг алгасна.

  3. 3.n = 1000 хот бүр бусадтайгаа шууд холбогдож болно, өртөг нь |xᵢ - xⱼ| + |yᵢ - yⱼ|. Edge-ийг хадгалалгүйгээр MST-г ол.

    Hint харах

    Edge нь 500 000 орчим. pq ашиглалгүй O(n²) Prim бич.

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

    dist[v] гэж tree хүртэлх хамгийн бага өртгийг хадгална. Алхам бүрт used биш, dist нь хамгийн бага node-ыг loop-оор олоод авч, бусдын dist-ийг шинэчилнэ. Нийт O(n²) = 1 000 000 үйлдэл.

Жишээ

Оролт

6 9
1 2 4
1 3 1
2 3 2
2 4 5
2 5 3
3 5 6
4 5 7
4 6 2
5 6 4

Гаралт

12

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.