P2323 [HNOI2006] Highway Construction Problem

OI island is a very beautiful island, and since its development, many people have come to travel here. However, because the island has only recently been developed, its transportation system is still poor. Therefore, the OIER Association was founded to build the transportation system of OI island. OI island has $n$ tourist attractions, labeled from $1$ to $n$. Now, the OIER Association needs to build roads to connect these attractions. A road connects two attractions. There are two types of roads, which we call Type 1 roads and Type 2 roads. Cars travel faster on Type 1 roads, but they cost more to build. The OIER Association plans to build $n-1$ roads to connect all attractions (so that there is a path between any two attractions). To ensure the efficiency of the road system, the OIER Association wants at least $k$ ($0 \le k \le n-1$) of these $n-1$ roads to be Type 1 roads. The OIER Association also does not want any single road to be too expensive. Therefore, under the above conditions, they want the cost of the most expensive road to be as small as possible. Your task is, given some candidate roads, to choose $n-1$ roads that satisfy the above conditions.

- The first line contains three numbers $n$ ($1 \le n \le 10000$), $k$ ($0 \le k \le n-1$), and $m$ ($n-1 \le m \le 20000$), separated by spaces. Here $n$ and $k$ are as described above, and $m$ means there are $m$ pairs of attractions between which a road can be built. - The following $m-1$ lines each contain four positive integers $a, b, c_1, c_2$ ($1 \le a, b \le n$, $a \ne b$, $1 \le c_2 \le c_1 \le 30000$), indicating that a road can be built between attractions $a$ and $b$. If a Type 1 road is built, the cost is $c_1$; if a Type 2 road is built, the cost is $c_2$. - In actual judging, there will be only $m-1$ road entries.

- The first line contains a single number, which is the cost of the most expensive road among the chosen roads. - The next $n-1$ lines each contain two positive integers $t$ and $p$. Here $t$ and $p$ indicate that on the $t$-th pair of attractions in the input (indexed from $1$ in input order), a Type $p$ road is built. - The $n-1$ lines must be output in increasing order of $t$. If multiple solutions achieve the minimal value of the maximum road cost, output any one of them.

Translated by ChatGPT 5