مساله «جاده‌ها»

یک کشور شامل N شهر و M جاده در نظر بگیرید. هر جاده یا سنگ‌فرش است یا آسفالت و دو شهر را به هم متصل می‌کند. می‌خواهیم بیشترین تعداد جاده از کشور را تخریب کنیم به طوری که از هر شهر بتوان به‌وسیله جاده‌های باقی‌مانده به هر شهر دیگر رفت. می‌خواهیم طوری این کار را انجام دهیم که دقیقا K تا از جاده‌های باقی‌مانده سنگ‌فرش باشند.

به شما مقادیر N، M، K و اطلاعات جاده‌های کشور داده‌می‌شود. شما باید تعدادی از جاده‌ها را تخریب دارید به‌طوری که شرایط مساله برقرار شود. سپس جاده‌هایی را که باقی مانده‌اند را در خروجی چاپ کنید. همچنین اگر چنین زیر مجموعه‌ای از جاده ها وجود ندارد اعلام کنید مساله جواب ندارد.

می‌دانیم N از ۲۰،۰۰۰ بیشتر نیست. همچنین M‌ حداکثر ۱۰۰،۰۰۰ است و K بین ۰ تا N-۱ می‌باشد.

راه حل

به زبان گراف صورت سوال اینگونه می‌شود: یک گراف N راسی همبند با M یال به شما داده می‌شود. هر یال از گراف یا قرمز است یا آبی. یک زیر درخت فراگیر از گراف را بیابید که دقیقا K‌ یال آن آبی باشد.

اگر K‌ یال آبی از گراف را انتخاب کنیم که تشکیل دور ندهند. یال‌های انتخاب شده تشکیل تعدادی مولفه می‌دهند که باید توسط یال‌های قرمز همبند شوند. ممکن است نتوان با اضافه کردن یال‌های قرمز گراف گفته شده را همبند کرد. پس به دنبال K یال آبی می‌گردیم که مطمئن باشیم پس از انتخاب این K یال بقیه گراف را بتوان توسط یال‌های قرمز همبند کرد.

کل یال‌های قرمز را در نظر بگیرید. اگر گراف یال‌های قرمز x مولفه داشته باشد. می‌توانیم با x-۱ یال آبی آن را همبند کنیم. این x-۱ یال را در نظر بگیرید. الآن زیر مجموعه‌ای از یال‌های آبی را انتخاب کرده‌ایم که وجودشان در جواب مساله الزامی است (اگر نباشند گراف با یال‌های قرمز همبند نمی‌شود). پس اگر بیش از K‌ یال آبی انتخاب کرده باشیم مطمئن هستیم که جوابی برای مساله وجود ندارد. حال فقط یال‌های آبی انتخاب شده را در نظر بگیرید. تا وقتی که K یال آبی انتخاب نکرده‌ایم هر بار یک یال آبی انتخاب نشده که با اضافه شدنش دور ایجاد نمی‌شود را به مجموعه یال‌هایمان اضافه می‌کنیم. اگر با این عمل نتوانستیم K یال آبی را انتخاب کنیم مساله جواب ندارد (چون بیشترین تعداد ممکن از یال‌های آبی را انتخاب کرده‌ایم که تشکیل دور نمی‌دهند). تا الآن K‌ یال آبی انتخاب کرده‌ایم که تشکیل دور نمی‌دهند. خاصیت K یال انتخاب شده این است که مولفه‌های گراف فعلی را می‌توان توسط یال‌های قرمز همبند کرد. چون اگر تمام یال‌های قرمز را به گراف فعلی اضافه کنیم گراف همبند می‌شود (زیرا در ابتدا تعدادی یال آبی انتخاب کردیم تا قرمز‌ها همبند شوند). پس به ترتیب هر یال قرمز را اضافه می‌کنیم اگر دو مولفه از گراف را به هم وصل بکند. در انتها زیر درخت خواسته شده توسط مساله را تولید کرده‌ایم.

برای پیاده سازی اعمال گفته شده در صورت مساله مناسب ترین راه استفاده از ساختار داده DSU (Disjoint Set Union) می‌باشد. برای اطلاع از نحوه کار این ساختار داده می‌توانید مقاله مرتبط با آن را بخوانید. همچنین برای مثالی از کاربرد این ساختار داده در حل مساله‌ها مقاله مربوط به الگوریتم کروسکال را بخوانید.

این سوال در دو سایت برنامه‌نویسی زیر برای حل کردن موجود است:

• Clearing Up
• المپیاد انفورماتیک آسیا-اقیانوسه ۲۰۰۸ - Roads