المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۴۳

Bipartite

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

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

ورودی

  • در سطر اول ورودی ۳ عدد $n$، $m$ و $e$ که به ترتیب نمایانگر تعداد راس‌های بخش اول، بخش دوم و تعداد یال‌های گراف است.
  • سپس در $e$ خط بعدی هر خط نمایانگر یک یال گراف است.
  • $1 \leq n, m \leq 500$
  • $1 \leq e \leq n*m$

خروجی

در سطر اول خروجی تعداد یال‌های انتخاب‌شده را بنویسید. در سطر بعد شماره‌ی یال‌های انتخاب‌شده را بنویسید. (یال‌ها به ترتیبی که در ورودی آمده‌اند از $1$ تا $e$ شماره‌گذاری شده‌اند)

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5 5 14
1 2
1 3
1 4
1 5
2 1
2 5
3 1
3 5
4 1
4 5
5 1
5 2
5 3
5 4
12
1 2 3 5 6 7 8 9 10 12 13 14

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه