المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:عملی:سوال ۱۸

سوال ۱۸

در گراف ساده‌ی $G$ به هر یال $e$ عدد $w_e$ نسبت داده شده، همچنین هر کدام از یال‌های آن با یکی از دو رنگ سیاه و سفید رنگ شده است که آن را با $c_e$ نشان می‌دهیم. گراف $G$ و به همراه $w$ و $c$ تمام یال‌ها و راس $s$ و راس $t$ به شما داده می‌شوند، شما باید مسیری از $s$ به $t$ پیدا کنید که هزینه‌ی آن بهینه باشد. هزینه‌ی یک مسیر برابر است با مربع مجموع وزن‌های یال‌های سیاه آن مسیر به اضافه تعداد یال‌های سفید آن مسیر. یعنی:

$$l(P)=\Biggl( \sum_{e \in P,c(e)=black} w_e \Biggr)^2 + |\{e \in P |c(e)= white\}|$$

و شما $l(P)$ که می‌یابید بین $s$ و $t$‌ است را کمینه کنید.

ورودی

برای گراف $G$ ماتریس $A$ به این صورت تعریف می‌شود که در صورتی که عنصر سطر $i$ و ستون $j$ ماتریس $A$، عدد $x$ باشد، اطلاعاتی که از این عدد به‌دست می‌آید به این صورت است:

  • صفر بودن $x$ به معنای عدم وجود یال بین راس $i$ ام و راس $j$ ام است.
  • $|x|$ نشان‌دهنده‌ی وزن یال بین راس $i$ ام و راس $j$ ام است.
  • مثبت بودن $x$ به معنی سیاه بودن یال مورد نظر است.
  • منفی بودن $x$ به معنی سفید بودن یال مورد نظر است.

در فایل ورودی نخست $n$ تعداد راس‌های گراف و سپس شماره‌ی راس‌های $s$ و $t$ به همین ترتیب آمده. سپس در $n$ سطر بعدی نیمه‌ی پایین ماتریس $A$ آمده.($2\leq n \leq200$ و $1\leq w_v\leq 200$)

خروجی

در فایل خروجی نخست $l(P)$ را بنویسید. و در سطر بعد نخست تعداد راس‌های مسیر $P$ سپس به ترتیب شماره‌ی راس‌هایی که در مسیر از $s$ به $t$ آمده‌اند را بنویسید. راس $t$ و $s$ را نیز بنویسید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
5 1 3
1
0 1
0 0 -1
-1 0 0 1
3
4 1 5 4 3

ابزار صفحه