Crimes in city of Megacity are going high. To fight the crimes, the authorities have created a
highway patrol. The city consists of a number of one-way roads. At the ends of each road, there
is a base station for the patrol troops. Each base station has a number of troops. At the beginning,
each station sends a troop along all the outgoing highways from that station. The troop patrols
the highway and whenever it reaches the station on the other side of the highway, it waits there,
and the troop that has been waiting there the most, is sent along the highway that has not been
patrolled the longest time.
Soon, they faced some difficulties, cause, the frequency of patrolling a highway is more and
more dependent on the number of highways that started and ended at the base station. If the
number of highways started at a base station is more than the number of highways ended there,
the roads are patrolled less frequently. And if, no highways end at some base station, then, the
highways started from there, will not be patrolled more than once.
In this situation, the highway patrol decided to remove some highways from the patrolling
schedule, so that, at each base station, the number of highways started and ended at any base
station will be equal. The rest of the highways will be monitored using video surveillance. But,
due to some security issues, there are some highways that have to be patrolled.
Now, given the cost of patrolling highways, and that of installing video surveillance, find the
minimum cost of monitoring the whole city. Please keep in mind that, video surveillance can not
substitute the highway patrol completely. So, there has to be at least one highway that will be
patrolled.
First line of the input contains an integer T(T≤ 70), the number of test cases. This is followed by
T test cases. Each test case starts with two integers N(1 ≤ N ≤ 100) and M(1 ≤ M ≤ 1000), the
number of base stations and highways. This is followed by M lines, each containing 5 integers,
u,v,p,s,x(1 ≤ u,v ≤ N,0 ≤ p,s ≤ 1000000) where u and v means, the highway starts from base
station u, and ends at v, p is the cost of patrolling and s is the cost of installing video
surveillance. If the highway must be patrolled, then x will be one. Otherwise it will be zero.
For each test case, output the case number, followed by the minimum cost to monitor the
highways. If it is not possible to patrol satisfying the given constraints, output “impossible”
(without quotes).
2 4 5 1 2 10 25 0 2 3 10 5 0 3 1 10 5 0 2 4 10 5 0 4 3 30 5 0 4 5 1 2 10 25 0 2 3 10 5 0 3 1 10 5 0 2 4 10 5 0 4 3 30 5 1
Case 1: 40 Case 2: 65
Migrated from old NTUJ.
2009Phuket
| No. | Testdata Range | Score |
|---|