Challenger

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

Challenger

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

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

پاسخ پرسش CF-111-D

دوشنبه, ۲۰ آذر ۱۳۹۱، ۰۹:۲۹ ب.ظ

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" را چاپ کنید .


شرح راه حل :
از کروسکال و پیدا کردن یال های برشی برای حل سوال استفاده می کنیم ...

کد ++C
موافقین ۵ مخالفین ۱ ۹۱/۰۹/۲۰

نظرات  (۲)

۰۴ دی ۹۱ ، ۱۳:۵۰ اکبر جوجه
من اصن نمیدونستم بلاگ داری!!!! خرکیف شدم دیدم بلاگتو! یه اطلاع رسانی کن آقا!
پاسخ:
:D
آقا اصن فعال نیستیا!!!!
پاسخ:
یکم درگیر کارای بچه های یزد هستم ، وقت نمی کنم تو بلاگ مطلب بزارم :)
ایشاا... از ماه دیگه بلاگ رو جمع و جور می کنم

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی