C. Алдаатай урсгал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эмускалд өөрийгөө урсгалын алгоритмын мастер гэж үздэг. Тэр чиглэлгүй граф дахь хамгийн их урсгалыг тооцоолдог өөрийн хамгийн чадварлаг програмаа дуусгачихаад байгаа. Граф нь $n$ орой ба $m$ ирмэгтэй. Оройнууд $1$-c $n$ хүртэл дугаарлагдсан. $1$ ба $n$ дугаартай оройнууд нь харгалзан эх болон төгсгөлийн орой болно.

Гэсэн ч түүний хамгийн их урсгалын алгоритм бага зэрэг алдаатай юм шиг санагдсан. Түүний алгоритм зөвхөн ирмэг бүрийн хувьд урсгалын хэмжээг олдог ба чиглэлийн хувьд олдоггүй. Үр дүнд гарч ирж байгаа урсгал зөв хамгийн их урсгал байх ёстой.

Илүү тодорхой хэлбэл танд чиглэлгүй граф өгөгдсөн. Графын чиглэлгүй ($a_{i}$, $b_{i}$) ирмэг бүрийн хувьд танд урсгалын хэмжээ $c_{i}$ мэдэгдэж байна. Та бүх ирмэгүүдийг дараах нөхцөлүүд биелэж байхаар чиглүүлэх ёстой:

  1. $v$ $(1 < v < n)$ орой бүрийн хувьд орж буй ирмэгүүдийн $c_{i}$ нийлбэр нь гарч байгаа ирмэгүүдийн $c_{i}$ нийлбэртэй тэнцүү байх;
  2. $1$ дугаартай оройруу орох ирмэг байхгүй байх;
  3. гаргаж авсан чиглэлтэй граф ямар ч циклгүй байх.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $m$ ($2 ≤ n ≤ 2*10^{5}$, $n - 1 ≤ m ≤ 2*10^{5}$) байх буюу графын орой болон ирмэгүүдийн тоо юм. Дараагийн $m$ мөр бүрт гурван бүхэл тоо $a_{i}$, $b_{i}$ ба $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$, $1 ≤ c_{i} ≤ 10^{4}$) байх ба $a_{i}$ болон $b_{i}$ оройнуудын хооронд $c_{i}$ хэмжээтэй урсгал бүхий чиглэлгүй ирмэг байгааг илтгэнэ.

Ижилхэн оройнуудыг холбох ямар ч хоёр ирмэг байхгүй; өгөгдсөн граф холбогдсон граф байна; шийдэл үргэлж оршин байна.

Гаралт

Тус бүрдээ нэг бүхэл тоо $d_{i}$-г агуулсан $m$ мөр хэвлэнэ. Хэрвээ $i$-р ирмэгийн чиглэл $a_{i} -> b_{i}$ байвал (урсгал маань $a_{i}$ оройгоос $b_{i}$ оройруу чиглэсэн) уг тоо 0 байх бол бусад тохиолдолд 1 байна.

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

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 3
3 2 10
1 2 10
3 1 5
Гаралт
1
0
1
Оролт
4 5
1 2 10
1 3 10
2 3 5
4 2 15
3 4 5
Гаралт
0
0
1
1
0

Тэмдэглэл

Эхний жишээн дээр замаар 10 нэгж урсгал урсах ба буюу эхлэлээс төгсгөлрүү 5 нэгж урсгал урсана.

Сэтгэгдлүүдийг ачааллаж байна...