بازرگانان نمکستان
بازرگانان نمکستان ، برای جبران خسارت جنگ ، تصمیم به تاسیس شرکتی کردند.
. در این شرکت
n کار و n کارمند وجود دارد که هر کارمند میتواند هر یک از کارها را انجام دهد. اما هزینه انجام هر کار توسط هر کارمند متفاوت است. از آنجایی که بازرگانان نمکستان تا به امروز ضرر و زیانهای مالی زیادی دیده اند میخواهند همه کارهای شرکت با کمترین هزینه ممکن انجام شود.
شما باید به آنها کمک کنید که به هر کارمند کدام کار را محول کنند تا هزینه صرف شده برای کارمندان به حداقل برسد و اوضاع آن ها کمی سر و سامان بیابد!
ورودی
- خط اول: عدد n (تعداد کارمندان و کارها)
- در خط های بعد ، جدولی از اعداد داده میشود .
خط اول مربوط به هزینه های کارمند اول و خط دوم مربوط به هزینههای کارمند دوم است و ...
خروجی
شما باید در هر خط مشخص کنید که هر کارمند باید چه کاری را انجام دهد
برای فهم بیشتر به مثال دقت کنید
مثال :
نمونه :
4
8 7 2 9
7 3 4 6
8 1 8 5
4 9 6 7
این جدول نشان میدهد که اگر کارمند اول ، کار اول را انجام دهد ، هزینه برای انجام آن کار 9 خواهد بود
اگر کارمند اول ، کار دوم را انجام دهد ، هزینه برای انجام آن کار 2 خواهد بود
اگر کارمند اول ، کار سوم را انجام دهد ، هزینه برای انجام آن کار 7 خواهد بود
اگر کارمند اول ، کار چهارم را انجام دهد ، هزینه برای انجام آن کار 8 خواهد بود
پس فعلا بهتر است کارمند اول کار دوم را انجام دهد . زیرا هزینه ی کمتری خواهد داشت .
اما باید توجه داشته باشیم اگر کارمند اول ، کار دوم را انجام دهد ، دیگر کارمند ها نمیتوانند آن کار را انجام دهند .
پس اگر قرار باشد کارمند اول کار دوم را انجام دهد ، بقیه ی کارمند ها فقط حق انتخاب بین کار های 1 ، 3 و 4 ام را دارند
خروجی نمونه
2
1
3
4
کمترین هزینه برای انجام کار ها این است که کارمند اول کار دوم را انجام دهد (2 هزینه)
کارمند دوم کار اول را انجام دهد (6+2 هزینه)
کارمند سوم کار سوم را انجام دهد (1+6+2 هزینه)
کارمند چهارم کار چهارم را انجام دهد (4+1+6+2 هزینه)
ترتیبی غیر از این ترتیب ، هزینه ای کمتر نخواهد داشت .
پس این ترتیب ، بهینه ترین است
به این زیر مسئله ها پاسخ دهید :
3
3 2 1
2 8 4
1 2 3
5
1 2 6 5 4
4 2 1 3 5
1 2 9 8 7
7 5 1 2 3
8 3 4 2 1