المپدیا

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

ابزار کاربر

ابزار سایت


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

Graph

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

ورودی

  • ورودی با $2$ عدد صحیح به صورت $N \ M$ شروع خواهد شد. $N$ تعداد راس‌ها و $M$ تعداد یا‌ل‌های گراف می‌باشد.
  • در خط $i$ام از $N$ خط بعدی یک عدد صحیح که وزن راس شماره $i$ را نشان می‌دهد، آمده است.
  • در هر یک از $M$ خط بعدی سه عدد طبیعی به صورت $i \ j \ k$ امده است که $i$ و $j$ بیان‌گر راس‌های دو سر یال و $k$ وزن آن یال می‌باشد.
  • $1 \leq N \leq 500$
  • $0 \leq M \leq 10000$

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه