پاسخ - SGU 158

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

ترجمه :

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

Topological Sorting - مرتب سازی توپولوژیکی

شرح مساله(ویکی پدیا) :

« در نظریه گرافها، یک مرتب سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گره‌هایی می‌آید که از آن به آنها یال خارج شده است. »

 

شرح الگوریتم : 

در هر مرحله می توانیم راس هایی را که هیچ یال ورودی ایی ندارند را در لیست قرار بدهیم

پس در هر مرحله همه راس هایی که هیچ یال ورودی ندارند (درجه ورودی آنها صفر است) را در لیست قرار می دهیم و لیست جدیدی از راس هایی که با حذف راس های قبلی درجه ورودی آنها صفر شده است درست می کنیم . حالا الگوریتم رو روی گراف جدید و با لیست جدید دوباره تکرار می کنیم .