406798: GYM102558 E Разделение графа
Description
Дан взвешенный неориентированный граф $$$G$$$, содержащий $$$n$$$ вершин и $$$m$$$ ребер.
Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.
Гарантируется, что граф не содержит петель и его нельзя разбить так, чтобы такого ребра не существовало.
Входные данныеВ первой строке задано число вершин $$$n$$$ ($$$3 \leq n \leq 10^5$$$) и число ребер $$$m$$$ ($$$3\leq m \leq 10^5$$$) графа.
В следующих $$$m$$$ строках заданы ребра в формате $$$u$$$, $$$v$$$, $$$w$$$ ($$$1\leq u, v \leq n$$$, $$$u\neq v$$$, $$$1 \leq w \leq 10^5$$$), где $$$u$$$ и $$$v$$$ задают начальную и конечную вершину ребра, а $$$w$$$ — его вес.
Выходные данныеВ единственной строке выведите максимальный возможный вес ребра, которое имеет минимальный вес среди тех, что соединяют вершины, принадлежащие одному множеству.
ПримерыВходные данные3 4 1 2 1 1 2 2 1 3 3 3 2 4Выходные данные
4Входные данные
4 5 1 2 1 2 3 1 3 4 1 4 1 1 2 4 2Выходные данные
2Примечание
Рассмотрим первый пример из условия. В нём возможно всего 3 различных разбиения, удовлетворяющих условию, рассмотрим каждое из них:
- $$$\{\{1, 2\}, \{3\}\}$$$, в таком случае рёбра $$$1$$$ и $$$2$$$ будут будут соединять вершины из одного множества, то есть ответ $$$1$$$;
- $$$\{\{1, 3\}, \{2\}\}$$$, в таком случае только ребро $$$3$$$ будет соединять вершины из одного множества, то есть ответ $$$3$$$;
- $$$\{\{2, 3\}, \{1\}\}$$$, в таком случае только ребро $$$4$$$ будет соединять вершины из одного множества, то есть ответ $$$4$$$.
Получаем, что ответ на тест достигается при третьем варианте разбиения.
Во втором тесте ответ достигается на разбиении $$$\{\{1, 3\}, \{2, 4\}\}$$$. Легко убедиться, расписав все возможные разбиения, что не существует разбиения данного графа, на котором ответ был бы больше.