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

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

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

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

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

MSU-ын Кибер Механик-ийн хэлтсийн төрийн албан хаагчийн элсэлтийн шалгалт дээр Саша Форд-Фулкерсоны алгоритмын талаарх нэгэн асуулттай тулгарчээ. Тэрээр программчлалын тэмцээний үеэр уг алгоритмтай маш олон удаа таарч байсан учраас уг сэдвийн талаар маш сайн мэдэж байв. Уг асуултын даалгавар болгон түүнд алгоритмын ажлын урсгалыг дүрслэхийн тулд ашиглах ёстой хэсэгчлэн барьсан урсгал бүхий нэгэн сүлжээ өгөгджээ. Тэрээр маш хурдан текст бичих хэсгийг хийж дуусгасан бөгөөд тэрээр зөвхөн өгөгдсөн сүлжээ нь алдаатай болохыг ойлгохын тулд бодлогыг сайтар ажиглан суусан байна!

Танд эх болон хонхор гэж нэрлэгдэх $s$ болон $t$ гэсэн 2 ширхэг онцгой онцгой оройнууд бүхий $G(V, E)$ гэсэн чиглэлтэй граф өгөгдсөн гэж үзье. Бид $n$-ээр уг графын оройн тоог илэрхийлэх ба өөрөөр хэлбэл $n = |V|$ байна. Мөн $m$-ээр уг граф дахь чиглэлтэй ирмэгийн тоог илэрхийлэх ба өөрөөр хэлбэл $m = |E|$ байна. Бид уг бодлогод зориулан $1$ гэсэн оройг үргэлж эх орой байна гэж үзэх ба $n$ гэсэн оройг үргэлж хонхор орой байна гэж үзнэ. Түүнчлэн графын ирмэг $e$ болгоны хувьд бид багтаамжийн функц $c(e)$ болон урсгалын функц $f(e)$-ыг тодорхойлох юм. Хэрэв дараах нөхцөлүүд хангагдсан байвал $f(e)$ функцийг зөв урсгалыг дүрсэлж байна гэж үзнэ:

  1. байх ирмэг бүрийн хувьд урсгал нь сөрөг биш байх бөгөөд багтаамж буюу $c(e)$-аас хэтрэхгүй байна. Өөрөөр хэлбэл $0 ≤ f(e) ≤ c(e)$ байх юм.
  2. байх ба эх эсвэл хонхор орой биш байх ($v ≠ s$ ба $v ≠ t$) орой бүрийн хувьд $v$ орой уруу явж орж буй бүх ирмэгүүдийн нийлбэр урсгал нь $v$ оройгоос гарж буй бүх ирмэгүүдийн нийлбэр урсгалтай тэнцүү байна. Өөрөөр хэлбэл $v$ орой дээр ямар ч урсгал гацаж үлдээгүй байх юм.

Шалгалтын материалыг өнгөрсөн шөнө бэлдсэн болох нь тодорхой байсан бөгөөд уг асуулт дотор маш олон алдаа байв. Саша профессоруудын нэгнээс нь уг сүлжээг засаж өгөхийг эсвэл зөв асуулт асуухыг хүссэн боловч профессор төрийн албан хаагчийн оюутнууд өөрсдөө уг сүлжээг засаж чаддаг байх ёстой хэмээн хариулжээ. Профессор уг асуултыг амархан болгохыг хүсэхгүй байгаа учраас тэрээр Саша-гаас нийт өөрчлөлтийн тоо нь боломжит хамгийн бага байхаар уг сүлжээг засахыг хүсжээ. Саша ирмэг хасах, шинээр ирмэг нэмэх болон оршин байгаа ирмэгийн чиглэлийг өөрчлөх гэсэн үйлдлүүдийг хийж болохгүй байв. Түүний хийж болох цорын ганц үйлдэл нь багтаамжийн функц $c(e)$ болон урсгалын функц $f(e)$-г өөрчлөх байв. Түүнчлэн эдгээр функцуудын бүх утгууд нь сөрөг биш бүхэл тоонууд хэвээр үлдэх ёстой ажээ. Урсгалыг хамгийн их байлгах талаар ямар нэгэн шаардлага өгөгдөөгүй болохыг анхаарна уу.

Саша зөв урсгал үүсгэхийн тулд хийх ёстой $f(e)$ болон $c(e)$ функцуудын боломжит хамгийн бага нийт өөрчлөлтийн тоог олно уу. Нийт өөрчлөлтийн тоо гэдэг нь абсолют зөрүүнүүдийн нийлбэрийг хэлэх бөгөөд өөрөөр хэлбэл хэрэв шинэ функцууд нь $f^{ * }(e)$ болон $c^{ * }(e)$ байвал нийт өөрчлөлтийн тоо нь болох юм.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 100$, $0 ≤ m ≤ 100$) өгөгдөх ба эдгээр нь харгалзан графын оройны тоо болон ирмэгийн тоог тус тус илэрхийлнэ. Дараагийн $m$ ширхэг мөрийн мөр болгонд ирмэгүүдийн тайлбар өгөгдөх бөгөөд тус бүр нь 4-н ширхэг бүхэл тоо $u_{i}$, $v_{i}$, $c_{i}$ болон $f_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$, $0 ≤ c_{i}, f_{i} ≤ 1 000 000$)-аар өгөгдөх ба эдгээр нь тухайн ирмэгийн гарах оройн дугаар, тухайн ирмэгийг явж орох оройн дугаар, одоо байгаа багтаамж болон урсгалын утгуудыг тус тус илэрхийлнэ.

$1$ дугаартай орой нь эх байх бөгөөд $n$ дугаартай орой нь хонхор орой байна. Мөн түүнчлэн ямар ч ирмэг эх орой уруу явж ороогүй байх бөгөөд ямар ч ирмэг хонхор оройгоос гараагүй байна.

Өгөгдсөн граф нь ямар ч өөртөө-гогцоо агуулаагүй байх боловч олон тооны ирмэгүүд агуулсан байж болно.

Гаралт

Ганц бүхэл тоо хэвлэх ба энэ нь Саша зөв урсгал үүсгэхийн тулд хийх ёстой хамгийн бага нийт өөрчлөлтүүдийн тоог илэрхийлнэ.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээнд урсгал нь анхнаасаа зөв байх юм. Урсгал нь хамгийн их биш байгаа бөгөөд энэ нь хамгийн их байх шаардлагагүй болохыг анхаарна уу.

2-дахь жишээнд цор ганц ирмэгийн урсгалын утга нь уг ирмэгийнхээ багтаамжаас их байна. Бидэнд үүнийг засах 2 арга байх юм: багтаамжийг $2$ болтол ихэсгэх эсвэл урсгалыг $1$ болтол багасгах гэсэн 2 арга байна.

3-дахь жишээнд $2$-р орой уруу зөвхөн $1$ нэгж урсгал явж орох боловч $2$ нэгж урсгал уг оройгоос гарж байна. Нэгэн боломжит шийдэл бол 2-р ирмэг дээрх урсгалын хэмжээг $1$-ээс багасгах юм.

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

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