G |
Stream
My Contest Input: Standard Input Output: Standard Output |
During 2009 and
2010 ICPC world finals, the contest was webcasted via world wide web. Seeing
this, some contest organizers from Ajobdesh decided that, they will
provide a live stream of their contests to every university in Ajobdesh.
The organizers have decided that, they will provide best possible service to
them. But there are two problems:
1. There is no
existing network between universities. So, they need to build a new network.
However, the maximum amount they can spend on building the network is C.
2. Each link in
the network has a bandwidth. If, the stream’s bandwidth exceeds any of the
link’s available bandwidth, the viewers, connected through that link can’t view
the stream.
Due to the
protocols used for streaming, a viewer can receive stream from exactly one
other user (or the server, where the contest is organized). That is, if you
have two 128kbps links, you won’t get 256kbps bandwidth, although, if you have
a stream of 128kbps, you can stream to any number of users at that bandwidth.
Given C,
you have to maximize the minimum bandwidth to any user.
Input
First line of
input contains T(≤50), the number of test cases. This is
followed by T test cases.
Each test case
starts with an integer N,M,C(1≤N≤60,1≤M≤104,1≤C≤109),
the number of universities and the number of possible links, and the budget for
setting up the network. Each university is identified by an integer between 0
and N-1, where 0 is the server.
Next M lines
each contain 4 integers, u,v,b,c(0≤u, v<N, 1≤b,
c≤106, u!=v), describing a possible link from university u
to university v, that has the bandwidth of b kbps
and of cost c. All links are unidirectional.
There is a blank
line before each test case.
Output
For each test case, output the maximum
bandwidth to stream. If it’s not possible, output “streaming
not possible.”.
3 3 4 300 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 3 4 500 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 3 4 100 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 |
128
kbps 256 kbps streaming not possible. |
Problemsetter: Manzurur Rahman Khan, Special Thanks:
Jane Alam & Derek Kisman