Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
پیوندهای روزانه

۲ مطلب در آذر ۱۳۹۱ ثبت شده است

۲۰آذر

Codeforces / Round #111 / Problem D: Edges in MST

صورت اصلی سوال :http://www.codeforces.com/contest/160/problem/D

ترجمه :

درخت پوشای کمینه (MST) : یک درخت پوشای کمینه از یک گراف وزن دار ، یک زیر درخت پوشا از آن است که مجموع وزن یال های آن کمینه باشد . واضح است که یک گراف همواره حداقل یک MST دارد و نیز می تواند چند MST داشته باشد .

یک گراف همبند وزن دار ساده به شما داده می شود . شما باید برای هر یال تعیین کنید این یال در همه MST های گراف ظاهر می شود یا در حداقل یکی از آنها ظاهر می شود یا در هیچکدام از آنها ظاهر نمی شود .

ورودی :
در خط اول ورودی دو عدد n و m داده می شود (تعداد راس ها و یال های گراف)
( , )
سپس در m خط بعدی ، مشخصات یال های گراف می آید ، در خظ i+1 ام سه عدد ai,bi,wi می آید که به ترتیب دو سر یال i ام و وزن آن هستند .
 

خروجی :
m خط چاپ کنید ، در خط i ام اگر یال i ام در همه ی MST ها ظاهر میشود "any" را  ، اگر در حداقل یکی از MST ها ظاهر می شود "at least one" را و اگر در هیچکدام ظاهر نمی شود "none" را چاپ کنید .
محمد مهدی جهان آرا
۰۸آذر

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=158


ترجمه :

در یک کشور ، دولت تصمیم گرفته تا سیستم قطار های شهری را هوشمند بکند ، صرف نظر از همه ی ویژگی ها ، این سیستم باید قطار ها را در ایستگاه متوقف بکند . در هر قطار یک کامپیوتر متصل به یک رادار وجود دارد که موقعیت مسافران در ایستگاه را پیدا می کند کامپیوتر باید محل توقف قطار در ایستگاه را مشخص کند به طوری که مجموع فاصله مسافران از نزدیک ترین در ه قطار به آنها بیشینه باشد .
وظیفه ی شما این است که با گرفتن اطلاعات ایستگاه و محل قرار گیری مسافران بهترین مکان برای توقف قطار در ایستگاه را مشخص کند .
محمد مهدی جهان آرا