Deskripsi Untuk Soal Nomor 17 dan 19
DESKRIPSI CERITA
Pak Dengklek mendapat tugas untuk menyusun rencana pengadaan jaringan listrik di sebuah daerah yang masih terpencil. Pada daerah tersebut, terdapat N buah desa (dinomori dari 1 s/d N) yang belum mendapatkan aliran listrik sama sekali. Tujuan Pak Dengklek adalah agar semua desa tersebut mendapatkan aliran listrik. Untuk mencapai tujuan tersebut, Pak Dengklek akan membangun satu atau lebih pembangkit listrik di satu atau lebih desa. Dalam melaksanakan rencana pembangunan ini, Pak Dengklek akan dibantu oleh M buah perusahaan kontraktor (dinomori dari 1 s/d M) yang siap untuk ditugaskan untuk membangun pembangkit listrik.
Setiap desa memiliki tingkat kesulitan untuk dibangun sebuah pembangkit listrik di desa tersebut. Desa nomor ke-i memiliki tingkat kesulitan Ai (1 ≤ i ≤ N). Selain itu, setiap perusahaan juga memiliki tarif biaya untuk pembangunan sebuah pembangkit listrik. Perusahaan ke-i memiliki tarif Bi (1 ≤ i ≤ M). Apabila sebuah perusahaan memiliki tarif p dan akan membangun pembangkit listrik pada sebuah desa dengan tingkat kesulitan q, maka biaya yang diperlukan oleh perusahaan tersebut dalam membangun pembangkit listrik di desa itu adalah p × q. Lebih lanjut, dalam sebuah peraturan pemerintah, telah ditetapkan bahwa setiap perusahaan hanya boleh membangun maksimal satu pembangkit listrik saja.
Pak Dengklek juga memiliki data mengenai keterhubungan antar desa. Setiap pasang desa mungkin terhubung satu dengan yang lain menggunakan sebuah jalan (dua arah). Secara keseluruhan, terdapat K buah jalan yang masing-masing menghubungkan sepasang desa yang berbeda. Apabila satu desa telah mendapat aliran listrik, maka semua desa yang lain yang terhubung (baik secara langsung maupun tidak langsung) ke desa tersebut, juga akan mendapat aliran listrik, tanpa harus memiliki pembangkit listrik sendiri.
Pak Dengklek ingin merancang strategi pembangunan pembangkit listrik sedemikian rupa sehingga semua desa dapat teraliri listrik, dan total biaya yang diperlukan adalah sekecil mungkin. Dapatkah Anda membantu Pak Dengklek untuk mencapai tujuan tersebut?
Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.

Gambar di atas mengilustrasikan N = 6 buah desa (A, B, C, D, E, dan F) serta situasi keterhubungan antar desa-desa tersebut dengan adanya K = 5 jalan yang menghubungkan antar desa. Tingkat kesulitan dalam membangun sebuah pembangkit listrik di setiap desa ditunjukkan dengan sebuah angka di dalam lingkaran yang melambangkan desa tersebut. Misalnya, tingkat kesulitan membangun pembangkit listrik di desa A adalah 3, sedangkan tingkat kesulitan di desa F adalah 6.
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?
Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}
Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.
[Gambar: Graf tak berarah dengan 6 node (desa A-F). Setiap node memiliki angka di dalam lingkaran yang menunjukkan tingkat kesulitan: A=3, B=2, C=7, D=5, E=1, F=6. Sisi-sisi: A-B, A-C, A-D, B-D, D-F. Total K=5 jalan.]
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 Pak Dengklek untuk dapat mengalirkan listrik ke semua desa tersebut?
Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}
Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan total biaya terkecil yang harus dikeluarkan Pak Dengklek untuk mengalirkan listrik ke semua desa, dengan ketentuan sebagai berikut:
Format Masukan:
Baris pertama berisi tiga buah bilangan: N (banyaknya desa), M (banyaknya perusahaan), dan K (banyaknya jalan antar desa). Setiap desa diberi nomor 1 s/d N, sedangkan setiap perusahaan juga diberikan nomor 1 s/d M. Baris berikutnya berisi N buah bilangan bulat positif yang menyatakan tingkat kesulitan membangun pembangkit listrik di masing-masing desa (mulai dari desa nomor 1 s/d desa nomor N). Baris berikutnya berisi M buah bilangan bulat positif, menyatakan tarif dari perusahaan 1 s/d perusahaan M. K baris terakhir berisi masing-masing dua buah bilangan bulat, P dan Q, yang menunjukkan bahwa ada jalan (dua arah) yang menghubungkan desa nomor P dan desa nomor Q.
Format Keluaran:
Sebuah baris berisi sebuah bilangan bulat positif, menyatakan total biaya terkecil yang diperlukan oleh Pak Dengklek untuk membangun satu atau lebih pembangkit listrik, sedemikian rupa sehingga semua desa dapat teraliri listrik. Apabila tidak dimungkinkan untuk mencapai tujuan tersebut, dengan tetap memenuhi peraturan yang ada, maka keluarkan nilai -1.
Peringatan: Untuk dapat menjawab pertanyaan ini dengan benar, program Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
3 4 1 2 5 3 7 5 6 3 2 3 | 19 |
3 2 0 4 8 2 1 3 | -1 |
Penjelasan Contoh:
Pada kasus pertama, terdapat 3 desa, masing-masing dengan tingkat kesulitan 2, 5 dan 3. Terdapat 4 perusahaan, masing-masing dengan tarif 7, 5, 6 dan 3. Selain itu, terdapat satu buah jalan yang menghubungkan desa nomor 2 dengan desa nomor 3 (dengan tingkat kesulitan 3). Dalam hal ini, Pak Dengklek dapat meminta Perusahaan 4 (dengan tarif 3) untuk membangun pembangkit listrik di desa nomor 3 (dengan tingkat kesulitan 3) dengan biaya sebesar 3 * 3 = 9. Selanjutnya Pak Dengklek meminta Perusahaan 2 (dengan tarif 5) untuk membangun pembangkit listrik di desa nomor 1 (dengan tingkat kesulitan 2), dengan biaya sebesar 5 * 2 = 10. Desa nomor 2 tidak perlu dibangun pembangkit listrik lagi, karena akan mendapatkan aliran listrik dari desa nomor 3. Dengan demikian, seluruh desa telah teraliri listrik, dan total biaya yang diperlukan adalah 9 + 10 = 19. Tidak ada rencana pembangunan yang lain yang memenuhi peraturan dan tujuan yang telah ditetapkan, namun dengan total biaya lebih kecil dari 19, namun jawaban untuk kasus ini adalah 19.
Pada kasus kedua, terdapat 3 desa dan 2 perusahaan, namun tidak ada jalan sama sekali yang menghubungkan antar desa. Sehingga, tidak mungkin dibuat rencana pembangunan dimana setiap perusahaan hanya membangun maksimal 1 pembangkit listrik, dan semua desa dapat teraliri listrik. Oleh karena itu, jawaban pada kasus kedua ini adalah -1.
Batasan:
Untuk semua kasus uji berlaku:
Subtask 1 (20%)
Subtask ini hanya berisi satu kasus uji, yaitu sebagai berikut:
8 4 5 7 5 3 10 2 8 6 9 25 10 35 30 1 2 3 4 5 4 4 6 3 5 |
Subtask 2 (30%)
Pada subtask ini, dijamin bahwa:
Subtask 3 (50%)
Tidak ada batasan tambahan.
Masuk untuk menulis jawaban