Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Domestic Networks
Description Alex is a system administrator of The network expands and Alex has to design a new network segment. He has a map that shows apartments to connect and possible links. Each link connects two apartments and for each possible link its length is known. The goal is to make all apartments connected (possibly through other apartments).
Help Alex to solve a hard problem: make a new network construction plan with possible minimal cost. A plan consists of list of links to be made and cable category for each link (each link should be a single piece of cable of either 5 or 6 category). The cost of the plan is the sum of cost of all cables. The total length of cables of each category used in the plan should not exceed the quantity of the cable available in the shop. Input The first line of the input file contains two numbers: Following b — apartments that can be connected by the link and _{i}l — link length in meters (0 ≤ _{i}l ≤ 100). Apartments are numbered from 1 to _{i}n.The last line of the input file contains four integer numbers: q ≤ _{i}Output If all apartments can be connected with the available cable, output c — the category of the cable to make it of. Links are numbered from 1 to _{i}m in the order they are specified in the input file. If there are more than one optimal plans, output any of them.If there is no plan meeting all requirements, output a single word “ Sample Input 6 7 1 2 7 2 6 5 1 4 8 2 3 5 3 4 5 5 6 6 3 5 3 2 11 3 100 Sample Output 65 1 5 2 6 4 6 5 6 7 5 Source Northeastern Europe 2007, Northern Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator