یک کشور شامل N شهر و M جاده در نظر بگیرید. هر جاده یا سنگ‌فرش است یا آسفالت و دو شهر را به هم متصل می‌کند. می‌خواهیم بیشترین تعداد جاده از کشور را تخریب کنیم به طوری که از هر شهر بتوان به‌وسیله جاده‌های باقی‌مانده به هر شهر دیگر رفت. می‌خواهیم طوری این کار را انجام دهیم که دقیقا K تا از جاده‌های باقی‌مانده سنگ‌فرش باشند.
به شما مقادیر N، M، K و اطلاعات جاده‌های کشور داده‌می‌شود. شما باید تعدادی از جاده‌ها را تخریب دارید به‌طوری که شرایط مساله برقرار شود. سپس جاده‌هایی را که باقی مانده‌اند را در خروجی چاپ کنید. همچنین اگر چنین زیر مجموعه‌ای از جاده ها وجود ندارد اعلام کنید مساله جواب ندارد.
می‌دانیم N از ۲۰،۰۰۰ بیشتر نیست. همچنین M حداکثر ۱۰۰،۰۰۰ است و K بین ۰ تا N-۱ می‌باشد.
- ۵ نظر
- ۲۵ اسفند ۹۰ ، ۱۹:۲۱