Controls
Masukkan jaringan koneksi antar gudang.
MST: 10 | Kedua: 11
Deskripsi
Bearcu harus mencari cara paling murah kedua untuk menghubungkan semua gudangnya.
Algoritma Kruskal + Enumerasi
- Hitung MST dengan Kruskal (urutkan sisi, DSU)
- Coba hapus setiap sisi MST satu per satu, hitung ulang MST
- Ambil nilai minimum dari semua alternatif yang valid
Tautan Soal
Langkah Kruskal
| Sisi | Biaya | Status |
|---|---|---|
| 1-3 | 2 | ✓ Diambil |
| 5-3 | 2 | ✓ Diambil |
| 1-2 | 3 | ✓ Diambil |
| 4-3 | 3 | ✓ Diambil |
| 5-2 | 4 | ✗ Lewati |
| 2-3 | 5 | ✗ Lewati |
| 1-5 | 5 | ✗ Lewati |
| 4-5 | 9 | ✗ Lewati |
| 4-1 | 9 | ✗ Lewati |
| 4-2 | 10 | ✗ Lewati |
Graf Koneksi
Sisi MST Lainnya