Зоос цуглуулагч

2s

512MB

1423

0%

Graph Algorithms

Тоглоомд $n$ өрөө, тэдгээрийг холбосон $m$ туннель бий. Өрөө бүрт тодорхой тооны зоос байна. Эхлэх болон дуусах өрөөгөө чөлөөтэй сонгож болохоор байхад туннелиэр дамжин явж цуглуулж болох хамгийн их зоосны тоо хэд вэ?

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

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

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо: өрөө болон туннелийн тоо. Өрөөнүүд $1,2,\dots,n$ -ээр дугаарлагдсан.

Дараа нь $n$ бүхэл тоо $k_1,k_2,\ldots,k_n$ : өрөө тус бүрийн зоосны тоо.

Эцэст нь $m$ мөрөнд туннелиуд байна. Мөр бүрд $a$ , $b$ хоёр бүхэл тоо: $a$ өрөөнөөс $b$ өрөө рүү туннель бий. Туннель бүр нэг чиглэлтэй.

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

Нэг бүхэл тоо хэвлэ: цуглуулж болох зоосны хамгийн их тоо.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le k_i \le 10^9$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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