Custom Min Spanning Tree

Pohon rentang minimal kustom

Keterangan

Membangun pohon rentang dari data input harus mematuhi ketiga aturan dasar ini:

1. Grafik harus menjadi pohon dan berisi semua node.
2. Grafik harus berisi jumlah tepi maksimum yang mungkin dari beberapa panjang tertentu, terlepas dari biaya yang terkait dengan tepi tersebut.
3. Jumlah total panjang tepi grafik yang dihasilkan menghormati aturan pertama dan kedua harus diminimalkan.

Gambar 1. Skema kemungkinan koneksi antara node grafik. Kemungkinan koneksi digambarkan sebagai tepi. Koneksi yang dapat membentuk pohon spanning yang diinginkan disorot dengan warna merah. Kasus a), b), c) sesuai dengan contoh 1, 2, 3 di bawah ini. Dalam beberapa kasus (misalnya dalam kasus B dan C) lebih dari satu rentang pohon dapat memenuhi tuntutan masalah. Namun, semua pohon spaning tersebut memiliki panjang total yang sama. Kasus a) menggambarkan pentingnya Aturan 3. Ada yang mencakup pohon yang berisi tepi (1, 5) dan (5, 4) yang memenuhi aturan 2 tetapi tidak memenuhi aturan 3 karena total panjang salah satu dari mereka setidaknya 17.

Tugas

Daftar semua koneksi yang mungkin antara node dan panjang koneksi masing -masing diberikan. Hitung total panjang pohon spanning yang memenuhi ketiga aturan yang disajikan dalam deskripsi.

Kumpulan data untuk tugas tersebut dibuat oleh para guru dari Universitas Teknis Ceko untuk subjek 'algoritma lanjutan'.

Masukan

Baris pertama dari input terdiri dari dua bilangan bulat N dan M dipisahkan oleh ruang. Nilai n adalah jumlah node. Nilai M adalah jumlah kemungkinan koneksi antara pasangan node. Selanjutnya, ada garis M, di mana setiap baris mewakili satu koneksi yang mungkin. Garis berisi tiga bilangan bulat D1, D2, L dipisahkan oleh ruang, yang berarti bahwa panjang kemungkinan koneksi antara node D1 dan D2 sama dengan L. Detektor diberi nomor dari 1 ke N. Koneksi yang mungkin tercantum dalam urutan acak. Ini memegang N ≤ 30000 dan m ≤ 300000. Setiap panjang paling banyak 10^9.

Keluaran

Output adalah satu baris yang berisi panjang total minimum dari jaringan yang diperlukan. Hasilnya tidak lebih besar dari 2^60.

Contoh 1

Contoh 1 data input dan jaringan yang dihasilkan digambarkan dalam gambar 1 a).

Contoh 2

Contoh 2 data input dan jaringan yang dihasilkan digambarkan dalam gambar 1 b).

Contoh 3

Contoh 2 data input dan jaringan yang dihasilkan digambarkan dalam gambar 1 C).

Larutan

Tugas ini diimplementasikan di Java menggunakan algoritma pencari serikat yang dioptimalkan (dijelaskan di sini). Dalam algoritma ada versi yang dimodifikasi dari hashmap yang diimplementasikan oleh penulis Justin Couch, Alex Chaffee dan Stephen Colebourne. Hashmap ini hanya menggunakan bilangan bulat primitif dan bukan objek Java Integer, yang menghasilkan peningkatan kinerja.