Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲۰:سوال ۳

Trees

گراف همبند G به ما داده شده است. می‌دانیم هیچ 2 دور از این گراف دارای یال مشترک نیستند. یال‌های گراف G را به تعدادی درخت T1 تا Tk افراز کرده‌ایم (رئوس هر کدام از Tiها زیر مجموعه‌ای از رئوس G هستند). شما باید با حذف کم‌ترین تعداد از این درخت‌ها از گراف G کاری کنید که گراف حاصل دور نداشته باشد.

ورودی

  • ورودی با ۲ عدد صحیح به صورت N M شروع خواهد شد. N تعداد راس‌ها و M تعداد یال‌های گراف می‌باشد.
  • در هر یک از M خط بعدی سه عدد طبیعی به صورت uiviti آمده است که ui و vi بیانگر راس‌های دو سر یال و ti شماره درختی است که این یال (در افراز گراف به درخت‌ها) به آن تعلق دارد.
  • درخت‌ها از 1 تا k شماره‌گذاری شده‌اند.
  • 1N10000
  • N1M(3×(N1))/2
  • 1k10000

خروجی

در خروجی یک عدد صحیح که بیانگر حداقل تعداد درخت‌هایی که باید حذف شوند است را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
6 6
1 5 1‎
1 2 2‎
2 4 2‎
2 6 3‎
3 4 1‎
3 5 1‎
1

ابزار صفحه