Question
Terdapat N desa terhubung oleh jalan dua arah. Pak Dengklek membangun pembangkit listrik di beberapa desa. Jika desa teraliri listrik, semua desa yang terhubung langsung maupun tidak langsung juga teraliri.
Biaya membangun pembangkit di desa dengan kesulitan q oleh perusahaan ber tarif p = p × q. Satu perusahaan maksimal membangun 1 pembangkit. Tujuan: semua desa teraliri dengan biaya minimum.
Graf 6 desa, 5 jalan, tingkat kesulitan:
Desa A B C D E F Kesulitan 3 2 7 5 1 6 Jalan: A–B, A–C, B–C, B–D, E–F (2 komponen: {A,B,C,D} dan {E,F}).
Jika terdapat 3 perusahaan: Perusahaan 1 dengan tarif 10, Perusahaan 2 dengan tarif 6 dan Perusahaan 3 dengan tarif 7, berapakah total biaya terkecil yang harus dikeluarkan oleh Pak Dengklek untuk dapat mengalirkan listrik ke semua desa tersebut?
Jawab: …………………………… {tuliskan jawaban dalam bentuk angka saja}