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 dua perusahaan: Perusahaan 1 dengan tarif 5 dan Perusahaan 2 dengan tarif 7, lalu Pak Dengklek meminta Perusahaan 1 membangun pembangkit listrik di desa A dan Perusahaan 2 di desa E, maka seluruh desa akan teraliri listrik dari kedua pembangkit tersebut. Dalam hal ini, berapakah total biaya yang harus dikeluarkan oleh Pak Dengklek?
Jawab: …………………………… {tuliskan jawaban dalam bentuk angka saja}