A. Ямаа самнах (Сурагч XI-XII)
Нэгэн мянгат малчин N тооны ямаатай. Ямаагаа 1-ээс N хүртэл дараалан дугаарласан ба i-р ямааг самнахад T(i) нэгж хугацаа зарцуулдаг. Тодорхой тооны (M тооны) ямааг бусад ямаанаас заавал өмнө самнах шаардлагатай байдаг. Ямаагаа хурдан хамнахын тулд хангалттай тооны хүн ажиллуулахаар бэлдсэн байгаа. Мянгат малчин N тооны ямааг хамгийн багадаа ямар хугацаанд самнах дуусгахыг мэдэхийг хүсэж байна.
Оролтын файл
Эхний мөрөнд N -ямааны тоо, M хязгаарлалтын тоо хоёр нэг хоосон зайтай өгөгдөнө. Дараагийн N ширхэг мөр бүрд ямааг самнах хугацааг илэрхийлэх T(i) натурал тоо, дараагийн M ширхэг мөрөнд A дугаартай ямааг В дугаартай ямаанаас өмнө самнахыг илэрхийлсэн 2 тоо байрлана.
Шаардлага
Гаралтын файл
Нэг натурал тоо байрлана.
Хязгаарлалтууд:
- 1 ≤ N ≤ 200,000
- 0 ≤ M ≤ 200,000
- 1 ≤ T(i) ≤ 1,000,000,000
Дэд бодлого
| № | Дэд бодлого | оноо | Хязгарлалт | Тайлбар |
|---|---|---|---|---|
| 1 | Дэд бодлого -1 | 1 | \(1 ≤ N ≤ 10, M = 0\) | |
| 2 | Дэд бодлого -2 | 1 | \(1 ≤ N ≤ 100, 0 ≤ M ≤ 100\) | |
| 3 | Дэд бодлого -3 | 1 | Граф нь зөвхөн нэг гинж (chain) | |
| 4 | Дэд бодлого -4 | 1 | Мод (tree) бүтэц | |
| 5 | Дэд бодлого -5 | 1 | Нэмэлт хязгаарлалтгүй |
Оролт-1
3 1
10
5
6
3 2Гаралт-1
11Тайлбар
1, 3-р ямааг зэрэг самнана. 3-р ямааг самнаж дуусаад 2-р ямааг самнана. 5+6=11 нэгж хугацаанд ямаагаа самнаж дуусна
Comments