کشور یوتپیا توسط دو پادشاه اداره می‌شود. اخیراً به دلیل اختلاف سلیقه در حکمرانی، دو پادشاه تصمیم گرفتند کشور را به دو قسمت تقسیم کرده و هر کدام در یکی از قسمت ها حکمرانی کنند. در کشور یوتپیا تعدادی جاده مخصوص استفاده بازرگانان و تعدادی جاده مخصوص استفاده مردم عادی وجود دارد. به علت پراهمیت بودن این جاده‌ها دو پادشاه برای تقسیم کشور علاوه بر این که هر قسمت باید دارای حداقل یک شهر باشد، محدودیت هایی زیر را در نظر گرفتند:
توجه کنید که برآورده کردن هر شرط مستقل از شرط دیگر امکان‌پذیر است. شما باید برنامه‌ای بنویسید تا با گرفتن اطلاعات مربوط به کشور یوتپیا بررسی کند آیا تقسیمی وجود دارد که هر دو شرط را بر آورده کند؟
به ازای هر تست، در صورت قابل انجام بودن کار 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_1$ ، $c_2$ و $c_3$ را به‌دست آوریم و آن‌ها را مقایسه کنیم. این کار را می توان در زمان ${\cal O}(n + m^2)$ انجام داد.