Gesaan dan konteks
Setiap sisi berarah mempunyai kapasiti dan kos unit. Hantar sehingga had aliran dari s ke t, meminimumkan kos antara penyelesaian dengan aliran yang sama. Kembalikan aliran sebenar dan kos sambil mengendalikan sisi songsang sisa, kos negatif, sisi selari, sinki yang tidak boleh dicapai, dan limpahan integer (integer overflow).
Perkara yang diuji oleh penemu duga
- Sama ada anda membina sisi sisa dan kos songsang dengan betul.
- Sama ada anda boleh menggunakan laluan terpendek berturutan (successive shortest paths) atau keupayaan dengan sisi negatif.
- Sama ada anda memisahkan objektif aliran maksimum daripada pemecah seri kos minimum.
- Sama ada anda menyatakan kekompleksan, had limpahan, dan ujian berasaskan sifat (property-based tests).
Soalan penjelasan sebelum menjawab
Sahkan kapasiti dan kos integer, kitaran kos negatif yang dibenarkan, keperluan had tepat, saiz graf, dan batas kos. Sekiranya kitaran negatif dibenarkan, jelaskan sama ada pengurangan kos tanpa batas adalah sebahagian daripada model dan bagaimana keupayaan awal diperoleh.
Kerangka jawapan 30 saat
Bagi setiap sisi input, tambahkan sisi sisa ke hadapan dan sisi songsang berkapasiti sifar dengan kos yang dinegatifkan. Cari laluan terpendek s-ke-t secara berulang dalam graf sisa dan tingkatkan kekangan gentingnya (bottleneck) sehingga had dicapai atau tiada laluan yang tinggal. Jika kos boleh bernilai negatif, kira keupayaan awal dengan Bellman-Ford, kemudian wajarkan semula sisi supaya Dijkstra sah digunakan. Kekompleksan bergantung pada penguatan (augmentations) dan pelaksanaan laluan terpendek, bukan hanya pada kekompleksan aliran maksimum biasa.
Perbincangan mendalam langkah demi langkah
1. Struktur sisi sisa
Simpan destinasi, indeks songsang, kapasiti sisa, dan kos. Penguatan mengurangkan kapasiti ke hadapan, meningkatkan kapasiti songsang, dan menambah aliran didarab dengan kos kepada jumlah keseluruhan. Sisi songsang membolehkan laluan terkemudian membatalkan pilihan terdahulu, yang penting untuk kos optimum.
2. Laluan terpendek dan keupayaan
Dengan kos bukan negatif, Dijkstra adalah mencukupi. Dengan kos negatif tetapi tiada kitaran negatif, kekalkan keupayaan bagi setiap bucu, kira laluan terpendek menggunakan kos yang dikurangkan (reduced costs), kemudian kemas kini keupayaan. Jangan sekali-kali menggunakan Dijkstra biasa secara terus pada graf yang mengandungi sisi negatif.
3. Penguatan dan pemberhentian
Jumlah penguatan ialah nilai minimum bagi had yang tinggal, kekangan genting laluan, dan sebarang had kelompok. Berhenti apabila tiada laluan wujud dan kembalikan aliran sebenar; jika had tepat diperlukan, laporkan ketakbolehlaksanaan (infeasibility). Gunakan jenis integer yang luas dan periksa pendaraban sebelum mengumpul kos.
Contoh jawapan berkualiti tinggi
Saya akan menyimpan sisi sisa dalam senarai bersebelahan (adjacency lists) dan menambah setiap pasangan ke hadapan dan songsang bersama-sama. Gelung utama mencari laluan s-ke-t terpendek dalam kalangan sisi berkapasiti positif, menguatkannya, dan mengemas kini kos. Dijkstra berfungsi untuk kos bukan negatif; dengan kos negatif dan tiada kitaran negatif, kira keupayaan awal dan pastikan kos yang dikurangkan kekal bukan negatif. Hadkan setiap penguatan mengikut permintaan yang tinggal dan kekangan genting laluan. Sekiranya sinki tidak boleh dicapai, kembalikan aliran sebenar dan tandakan sasaran yang tidak dipenuhi sebagai tidak boleh dilaksanakan. Ujian merangkumi pembatalan songsang, sisi selari, kapasiti sifar, kos negatif, graf terputus, aliran separa, andaian kitaran negatif, dan limpahan kos besar. Model ini sepadan dengan formulasi aliran kos minimum OR-Tools, tetapi kekompleksan mesti menyatakan faktor bucu, sisi, dan penguatan; ia tidak secara automatik berbentuk polinomial dalam kapasiti berangka.
Kesilapan lazim
- Terlupa sisi songsang atau menetapkan kos positif padanya dan bukannya kos yang dinegatifkan.
- Menjalankan Dijkstra secara terus apabila sisi sisa boleh mempunyai kos negatif.
- Menguatkan hanya satu unit bagi setiap laluan terpendek tanpa justifikasi.
- Menganggap aliran maksimum dan kos minimum sebagai satu kunci pengisihan yang tidak dibezakan.
- Mengumpul nilai kapasiti-darab-kos yang besar dalam jenis integer yang sempit.
Soalan susulan dan jawapan
Mengapakah sisi songsang boleh membetulkan pilihan terdahulu?
Ia mewakili penarikan balik aliran yang dihantar sebelumnya dan menafikan kos aliran tersebut. Laluan terpendek yang terkemudian boleh menggunakannya untuk menyusun semula penyelesaian dan menurunkan jumlah kos.
Bilakah anda memerlukan Bellman-Ford?
Apabila graf sisa awal mempunyai sisi kos negatif tetapi tiada kitaran negatif, gunakannya atau kaedah yang setara untuk mengira keupayaan awal; selepas itu kos yang dikurangkan yang bukan negatif membolehkan penggunaan Dijkstra.
Bagaimana jika aliran yang diminta tidak dapat dicapai?
Berhenti dan kembalikan aliran sebenar serta kos dengan hasil tidak boleh dilaksanakan yang jelas. Sekiranya perniagaan memerlukan sasaran tersebut, pemanggil mesti membuat undur balik (roll back) atau memilih rangkaian sandaran dan bukannya menganggap aliran separa sebagai kejayaan.