Maximize the bandwidth of the least wide link

Reference no: EM133028243

Routing

Part I. Widest PathRouting

N large files (1≤N≤105), numbered 1...N, are scattered on N distinct storages throughout a network that connects these storages. These storages are also numbered 1...N, such that file fi is at storage si. M links (1≤M≤105), numbered 1...M, where link i bidirectionally connects storage aiwith storage bi, and has a bandwidth wi(1≤ai,bi≤N,ai ≠ bi,1≤wi≤109). Bandwidthwitakes on integer values.

At any point in time, two files located at twostorages directly connected by a link may simultaneously swap places through the link. That is, the file on storage acan be transferred to storage b and the file on b can be transferred to a using the link that connects a and b. The files must perform such swaps until fiis at storage i for 1≤i≤N. That is, the files must eventually be placed at their "rightful" storage using the network.

To reduce the time to accomplish the task of moving files to their rightful storages, you are asked to design and implement an algorithm to maximize the bandwidth of the least wide link which the file transfer must use to move the files to their "rightful" storages speedily. It is guaranteed that it is possible for the files to move to their rightful storages.

INPUT FORMAT (file storage.txt):

The first line has two integers, N and M. The second line contains the N integers s1s2,..., sN. It is guaranteed that one storage contains one file.

Line i+2 contains the integers ai, bi, and wiwhere1≤i≤M.
OUTPUT FORMAT (file storageout.txt):
Outputone integer number: the maximum minimal bandwidth of a link which a file must use to move itself to its "rightful" storage. If the files are already in their "rightful" storages, then output -1.
SAMPLE INPUT 1:
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
SAMPLE OUTPUT 1:
9
In this example, one can move the files as follows to their rightful storages using links of bandwidth at least 9.

File 1 and file 2 swap locations using the 3rd link.
File 1 and file 3 swap locations using the 1stlink.
File 2 and file 3 swap locations using the 3rd link.

Output one integer number: the maximum minimal bandwidth of a link which a file must use to move itself to its "rightful" storage

SAMPLE INPUT2:
4 1
1 2 3 4
4 2 13
SAMPLE OUTPUT 2:
-1

Attachment:- Routing lab.rar

Reference no: EM133028243

Questions Cloud

Prepare general journal entry to record the reimbursement : On October 15, the petty cash fund was replenished and increased to $1,500. Prepare general journal entry to record the reimbursement

Justification for making the process less rigorous : Balancing principles and pragmatism in selection Matt is an HR adviser with a large engineering company. The company has a comprehensive selection policy that r

What is the net present value of the project : A project that has been tested for its feasibility has already incurred market research costs of £50,000. What is the Net Present Value of the project

Identify potential causes of the problem : The Fantasy Sports Trade Association estimates that approximately 57.4 million people in the United States and Canada play fantasy football.

Maximize the bandwidth of the least wide link : Design and implement an algorithm to maximize the bandwidth of the least wide link which the file transfer must use to move the files to their "rightful" storag

Organizational learning and training and development : How does this connection help us understand why the performance appraisal training program was not more successful?

What would be the firm new debt ratio : If Campbell were to purchase a new warehouse for $1.2 million and finance it entirely with long-term debt, what would be the firm's new debt ratio

Approaches human resource personnel : (a) Based on the above statement, discuss THREE (3) approaches human resource personnel used to evaluate employees' working performance.

How much of the loan is paid off during the first year : This extended problem covers many of the features of a mortgage. You purchase a town house for $200,000. How much of the loan is paid off during the first year

User Account

All Pages