Даалгавар Хуваарилах

2s

512MB

1888

0%

Advanced Techniques

Компанид $n$ ажилтан, гүйцэтгэх шаардлагатай $n$ даалгавар байна. Ажилтан бүр даалгавар бүрийг гүйцэтгэх өртөг мэдэгдэнэ. Ажилтан бүрд яг нэг даалгавар оноох ёстой. Даалгавруудыг оновчтой оноовол хамгийн бага нийт өртөг хэд байх ба яаж оноох вэ?

https://cses.fi/problemset/task/2129

Оролтын формат

Эхний мөрөнд нэг бүхэл тоо $n$ байна: ажилчдын тоо ба гүйцэтгэх даалгавруудын тоо.

Дараагийн $n$ мөр бүр $n$ бүхэл тоо агуулна. $i$ дахь мөрөнд $c_{i1},c_{i2},\ldots,c_{in}$ бүхэл тоонууд байна: даалгавар бүрийг $i$ дахь ажилтанд оноох үеийн өртөг.

Гаралтын формат

Эхлээд хамгийн бага нийт өртөгийг хэвлэ.

Дараа нь мөр бүр нь хоёр бүхэл тоо $a$ , $b$ -ээс тогтох $n$ мөр хэвлэ: $a$ дахь ажилтанд $b$ дахь даалгаврыг оноосон.

Олон шийд байвал алийг нь ч хэвлэж болно.

Хязгаарлалт

$1 \le n \le 200$
$1 \le c_{ij} \le 1000$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...