Olimpiade Sains Provinsi (OSP) 2023 - Komputer, Nomor 17–19

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}

PEMBANGKIT LISTRIK

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:

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:

• 1 ≤ N, M ≤ 100 000
• 0 ≤ K ≤ 200 000
• 1 ≤ A_i ≤ 1 000 000
• 1 ≤ B_i ≤ 1 000 000
• Tidak ada jalan yang menghubungkan suatu desa dengan desa itu sendiri.
• Untuk setiap pasangan desa berbeda, hanya terdapat paling banyak satu jalan yang menghubungkan keduanya.

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:

• K = 0
• 1 ≤ A_i ≤ 100
• 1 ≤ B_i ≤ 100

Subtask 3 (50%)
Tidak ada batasan tambahan.