فهرست مندرجات
Generous Kings
کشور یوتپیا توسط دو پادشاه اداره می‌شود. اخیراً به دلیل اختلاف سلیقه در حکمرانی، دو پادشاه تصمیم گرفتند کشور را به دو قسمت تقسیم کرده و هر کدام در یکی از قسمت ها حکمرانی کنند. در کشور یوتپیا تعدادی جاده مخصوص استفاده بازرگانان و تعدادی جاده مخصوص استفاده مردم عادی وجود دارد. به علت پراهمیت بودن این جاده‌ها دو پادشاه برای تقسیم کشور علاوه بر این که هر قسمت باید دارای حداقل یک شهر باشد، محدودیت هایی زیر را در نظر گرفتند:
- تقسیم باید به گونه‌ای باشد که تعداد جاده‌های مخصوص بازرگانان بین دو قسمت کمینه باشد.
- تقسیم باید به گونه‌ای باشد که تعداد جاده‌های مخصوص مردم عادی بین دو قسمت کمینه باشد.
توجه کنید که برآورده کردن هر شرط مستقل از شرط دیگر امکان‌پذیر است. شما باید برنامه‌ای بنویسید تا با گرفتن اطلاعات مربوط به کشور یوتپیا بررسی کند آیا تقسیمی وجود دارد که هر دو شرط را بر آورده کند؟
ورودی
- در سطر اول ورودی عدد $t$ نشان‌دهنده تعداد تست‌هایی که برنامه شما با آن آزمون می‌شود آمده است.
- در سطر اول هر تست، عدد $1 \leq n \leq 100$ نشان‌دهنده تعداد شهرها آمده است.
- در سطر بعدی، دو عدد $1 \leq m_1 \leq 1000$ و $1 \leq m_2 \leq 1000$ نشان‌دهنده تعداد جاده‌های مخصوص بازرگانان و تعداد جاده‌های مخصوص مردم عادی آمده است.
- در $m_1$ سطر بعد، دو عدد $1 \leq u_i \leq n$ و $1 \leq v_i \leq n$ ($u_i \neq v_i$) آمده‌اند که نشان می‌دهند $i$امین جاده مخصوص بازرگانان بین دو شهر $u_i$ و $v_i$ قرار دارد.
- در $m_2$ سطر بعد، دو عدد $1 \leq a_i \leq n$ و $1 \leq b_i \leq n$ ($a_i \neq b_i$) آمده‌اند که نشان می‌دهند $i$امین جاده مخصوص مردم عادی بین دو شهر $a_i$ و $b_i$ قرار دارد.
- امکان دارد بین دو شهر بیش از یک جاده وجود داشته باشد.
خروجی
به ازای هر تست، در صورت قابل انجام بودن کار YES و در غیر این صورت NO چاپ نمایید.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 3 1 1 1 2 1 3 3 2 1 1 2 1 3 1 3 | No YES |
پاسخ
می توان مسئله را به صورت زیر شبیه‌سازی کرد:
گراف‌های $G$ ، $G_1$ و $G_2$ و رئوس $s$ و $t$ طوری به ما داده شده که مجموعه رئوس $G$ ، $G_1$ و $G_2$ برابرند و مجموعه یال‌های $G$ برابرست با مجموع یال‌های $G_1$ و $G_2$. اگر برش کمینه میان رئوس $s$ و $t$ در گراف‌های $G_1$ و $G_2$ به ترتیب برابر با $c_1$ و $c_2$ باشد آیا برشی بین رئوس $s$ و $t$ در $G$ وجود دارد که در آن حداکثر $c_1$ یال از $G_1$ و $c_2$ یال از $G_2$ وجود داشته باشد؟
فرض کنید اندازه این برش برابر باشد با $c$. برای حل سوال باید سه حالت زیر را بررسی کرد:
- $c \geq c_1+c_2+1$ : در این صوررت یا حداقل $c_1+1$ یال از $G_1$ در برش کمینه وجود دارد، یا حداقل $c_2+1$ یال از $G_2$، پس چنین برشی وجود ندارد.
- $c \leq c_1+c_2-1$ : چنین حالتی امکان‌پذیر نیست، زیرا برش کمینه حداقل باید $c_1$ یال از $G_1$ و $c_2$ یال از $G_2$ داشته باشد.
- $c = c_1 + c_2$ : در این صورت برش به دست آمده همان برشی است که سوال خواسته.
پس کافیست سه مقدار $c_1$ ، $c_2$ و $c_3$ را به‌دست آوریم و آن‌ها را مقایسه کنیم. این کار را می توان در زمان ${\cal O}(n + m^2)$ انجام داد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
