المپدیا

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

ابزار کاربر

ابزار سایت


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

Roads

به شما یک گراف ساده وزن‌دار همبند داده شده است. می‌خواهیم وزن یال‌های این گراف را طوری تغییر دهیم که به ازای هر یال یک دور (شامل آن یال) وجود داشته باشد که وزن آن یال از وزن هیچ یک از یال‌های آن دور کمتر نباشد. شما تنها می‌توانید وزن یال‌ها را افزایش دهید. کمترین مجموع تغییرات وزن‌ یال‌ها برای براورده کردن شرط فوق را بیابید.

ورودی

  • در سطر اول ورودی به ترتیب دو عدد طبیعی ‎$n$‎، تعداد‌ راس‌های گراف و ‎$e$‎، تعداد یال‌های آن آمده است.
  • هر یک از ‎$e$‎ سطر بعدی، به ترتیب شامل سه عدد طبیعی ‎$u$‎، ‎$v$‎ و ‎$w$‎ است که نشانگر یک یال از ‎$u$‎‌ به ‎$v$‎ با وزن ‎$w$‎ می‌باشد.
  • تضمین می‌شود که گراف داده شده در ورودی همبند است و گراف یال چندگانه و طوقه ندارد. همچنین تضمین می‌شود هر یال درون حداقل یک دور می‌باشد.
  • $2 \leq n \leq e \leq 10^5$‎.
  • $1 \leq u,v \leq n‎, ‎u \ne v$‎.
  • ‎ $1 \leq w \leq 10^9$‎.

خروجی

در تنها سطر خروجی پاسخ مسئله را چاپ کنید. دقت کنید که این مقدار ممکن است از ‎$2^{32}$‎ بیشتر شود.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۱۰ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^3$‎.
  • زیرمسئله‌ی دوم (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 10^3$‎ و ‎$e\leq 10^5$‎.
  • زیرمسئله‌ی سوم (۵۵ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^5$‎.
  • زیرمساله‌ی چهارم (۵ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^6$‎.

محدودیت‌ها

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

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

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


ابزار صفحه