Məsələlər
Median Tree
Median Tree
You are given a connected undirected graph which has even numbers of nodes. A connected graph is a graph in which all nodes are connected directly or indirectly by edges.
Your task is to find a spanning tree whose median value of edges' costs is minimum. A spanning tree of a graph means that a tree which contains all nodes of the graph.
\InputFile
The input consists of multiple datasets.
The format of each dataset is as follows.
\textbf{n m}
\textbf{s_1 t_1 c_1}
\textbf{...}
\textbf{s_m t_m c_m}
The fi rst line contains an even number \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{1000}) and an integer \textbf{m} (\textbf{n-1} ≤ \textbf{m} ≤ \textbf{10000}). \textbf{n} is the nubmer of nodes and \textbf{m} is the number of edges in the graph.
Then \textbf{m} lines follow, each of which contains \textbf{s_i} (\textbf{1} ≤ \textbf{s_i} ≤ \textbf{n}), \textbf{t_i} (\textbf{1} ≤ \textbf{s_i} ≤ \textbf{n}, \textbf{t_i} ≠ \textbf{s_i}) and \textbf{c_i} (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{1000}).
This means there is an edge between the nodes \textbf{s_i} and \textbf{t_i} and its cost is \textbf{c_i}. There is no more than one edge which connects \textbf{s_i} and \textbf{t_i}.
The input terminates when \textbf{n = 0} and \textbf{m = 0}. Your program must not output anything for this case.
\OutputFile
Print the median value in a line for each dataset.
Giriş verilənləri #1
2 1 1 2 5 4 6 1 2 1 1 3 2 1 4 3 2 3 4 2 4 5 3 4 6 8 17 1 4 767 3 1 609 8 3 426 6 5 972 8 1 607 6 4 51 5 1 683 3 6 451 3 4 630 8 7 912 3 7 43 4 7 421 3 5 582 8 4 538 5 7 832 1 6 345 8 2 608 0 0
Çıxış verilənləri #1
5 2 421