المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۲۶

مدیر زرنگ

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

ورودی

در سطراول فایل ورودی $n$ تعداد سناریو‌های مختلف آمده. در هر سناریو ابتدا $n$ تعداد کامپیوتر‌ها و $e$ تعداد مسیرهای ارتباطی بین کامپیوترها می‌آید.

سپس در هر یک از $e$ سطر بعدی، شماره‌ی کامپیوتر‌های دو سر یک مسیر و هزینه‌ی ایجاد ارتباط از این طریق ذکر شده.

خروجی

به ازای هر سناریو در یک سطر واژه‌ی YES یا NO را بنویسید.

توجه

  • کامپیوتر‌ها با شماره‌های ۱ تا $n$ نشان داده می‌شوند.
  • کامپیوتر مدیر با شماره‌ی ۱ نشان داده می‌شود.
  • تعداد سناریو‌ها حداکثر ۱۰ و $3\leq n \leq 1000$ و $1\leq e \leq 5 \times 10^5$ است.
  • هزینه‌ی اتصال‌ها نیز مثبت و کم‌تر از $10^6$ می‌باشند.

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

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

3 3
1 2 4
2 3 4
3 1 4

4 6
1 2 1
3 4 5
3 2 1
1 4 6
1 3 7
2 4 2
NO
YES

ابزار صفحه