پاسخ - SGU 143
متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=143
ترجمه :
تعدادی شهر داریم که بعضی از آنها به هم جاده دارند به طوری که از هر شهری می توان به هر شهر دیگر رفت و همچنین بین هیچ دو شهری بیشتر از یک مسیر وجود ندارد . برای هر شهر عددی را به عنوان "سود" داریم . می خواهیم تعدادی از شهر ها را انتخاب کنیم به طوری که در مجموعه شهر های انتخاب شده بتوان از هر شهری به هر شهر دیگر در مجموعه رفت و مجموع مقدار سود های همه ی شهر های انتخاب شده حداکثر شود .
ورودی :
در اولین خط ورودی تعداد شهر ها می آید N<=16 000
در خط بعدی N عدد می آید که i امین عدد میزان سود شهر i ام است .(سود می تواند منفی هم باشد)
خروجی :
در تنها خط خروجی پاسخ مساله یعنی حداکثر میزان سود مجموع را در یک مجموعه همبند از شهر ها را چاپ کنید .
شرح راه حل : با بهره گیری از الگوریتم DFS به پرسش پاسخ می دهیم ....
کد راه حل : http://snipt.net/JahanaraCo/sgu-143/
