Чорнозлив#2482
Дренажна система складається з дренажних канав на площині, які представлені відрізками, що з'єднують дренажні вузли. Ці канави перетинаються лише у дренажних вузлах, які є їхніми кінцями. Кожна канава має вказану пропускну здатність, тобто максимальну кількість одиниць рідини, що може пройти через неї за одиницю часу. Існує спільний дренажний вихід у певному дренажному вузлі . Рідина може текти через канаву в будь-якому напрямку, але лише в одному напрямку одночасно.
Канави розділяють площину на кілька областей, у тому числі робочі області (зовнішня область також вважається робочою). Василь перебуває зараз в одній із цих областей, на межі якої знаходиться спільний дренажний вихід. Проте через технічні обмеження він не може скористатися виходом безпосередньо. Терміново потрібно злити вершкове масло через канави, щоб воно дійшло до дренажного вузла . Для цього Василь планує зливати масло в певний вузол . Вважається, що масло розтікається миттєво, і через жодну канаву не може пройти більше одиниць масла, ніж її пропускна здатність. Необхідно визначити, яку максимальну кількість одиниць масла за одиницю часу Василь зможе злити.
У першому рядку введено кількість дренажних вузлів , кількість дренажних канав , вузол, яким користується Василь , і дренажний вузол зі спільним виходом (1 \leq n \leq 50000, 1 \leq m \leq 3n, 1 \leq s, t \leq n, s \neq t). У наступних рядках задано координати дренажних вузлів x_i y_i — цілі числа, модуль яких не перевищує 10^9. Жодні два вузли не знаходяться в одній точці. Далі описано дренажних канав у форматі u_j v_j w_j (1 \leq u_j, v_j \leq n, u_j \neq v_j, 1 \leq w_j \leq 10^6) — це канава між вузлами u_j та v_j з пропускною здатністю w_j. Гарантується, що канави не перетинаються у внутрішніх точках, а також що вузли і доступні з тієї області, де перебуває Василь, за умови нормального дренажу. Між будь-якою парою вузлів є не більше однієї канави.
Виведіть максимальну кількість вершкового масла, яку Василь може злити за одиницю часу.
Приклад 1