程序设计在线评测(Online Judge)


问题 1063. -- 2010欧洲西南分区赛:Sensor network

1063: 2010欧洲西南分区赛:Sensor network

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 0
[提交][状态][讨论版]

题目描述

In response to a request by the SWERC 2010 problem-setting team, a sensor network has just been installed
in the headquarters. The organizing committee has put in the problem-setters the disproportionate fear of
su ering a leak of classi ed information about the problems.
Nevertheless, in the rush they forgot to think about the electricity network needed to make the sensors
work. Because of this, the security system is currently not working, but we need to justify the great amount
of resources invested in it, so the installation must be ready before the end of the contest. Hence you are
now asked to elaborate a program which will help the electrician in his duty.
Since the organizing committee spared no expense, they ordered the sensors from a prestigious company.
Every sensor is handcrafted and a number is written on each of them, whose meaning is the recommended
voltage that should be applied to it for correct operation. They can be used under higher voltages, with
an increasing risk of failure, but never with a voltage below the recommended one. The electrician gazed
open-mouthed at the sensors when they were given to him: nearly all of them had di erent recommended
voltages! The sensors were installed in the building in such a way that each of them controls exactly two
doors and every door is controlled by at least one sensor. Now is the time for the electrician to supply power
to the sensors. He faces the following constraints:
 Fortunately, there is no need to activate all sensors. However, we will require that the subset of sensors
chosen to be on satisfy that every door is controlled by, at least, one sensor in the subset.
 Electricity is to be supplied to one of the active sensors, and then distributed to the others with wires.
In order not to waste wires, they can only be installed by connecting a pair of neighboring active
sensors (by \neighbouring" we mean that some door is controlled by both of them). Since we must
supply energy to every active sensor, not every subset of sensors is suitable as the chosen subset of
working sensors.
 Because of the above, all of the sensors will be supplied the same voltage, which cannot be below the
corresponding recommended voltages.
For simplicity, we will refer to a subset of sensors satisfying the rst two constraints above as an admissible
subset. The network is designed so that the set of all sensors is always admissible, but we would like to take a
possibly smaller subset so as to minimize the margin, de ned as the maximum of the di erences, in absolute
value, between the numbers written on each pair of sensors in the subset. (This is to keep the chances of
failure to a minimum).
The electrician could not solve the task of nding the admissible subset of the set of sensors for which
the margin is minimum. Therefore, the electrical installation is still missing. Today, we ask you to write a
program to nd out the answer, given a sensor network and the recommended voltage for each of the sensors.

输入

The input consists of several test cases, separated by single blank lines. Each test case begins with a line
containing the integer n (2  n  350), the number of doors in the building. The following line contains
another integer, m (n

输出

For each case, your program should output a line containing the minimum margin of an admissible subset
of the sensors.

样例输入

3
3
0 1 220
1 2 120
2 0 160

4
5
2 3 80
1 3 80
0 1 180
2 1 200
3 0 140

0

样例输出

40
60

提示

来源

[提交][状态][讨论版]