No one knows about NSIT
All submissions for this problem are available.
Gande has joined NayaSa Institute of Technology also abbreviated as NSIT and he is very happy about being in one of the highly rated college. As you might guess by the title , NSIT is very unpopular.
Someday some guy came from the land of “The World was there” and after underestimating Gande, challenged him to solve a so called brutal problem which was never solved in their world.
The problem states that given N servers and N-1 bidirectional wires you have to connect them all such that there is a path between every server (directly or indirectly). Now, out of N-1 wires each wire has a length C. Any wire can be used to connect any pair of the given N servers. The cost of the network is calculated in two terms:
- Sum of lengths of all the wires used to connect.
- Sum of degree(u) * degree(v) for all ordered pairs u,v such that u!=v (u and v are servers)
The cost of the network is sum of the above two terms.
Gandey has to maximise this cost.
Although being a student of NSIT, Gandey can easily solve this problem very quickly but he has plans with Ms. Ghatak ! So , please solve this problem while Gandey and Ghatak are watching movie.
- Indirect connection means that if u and v are connected , and , v and w are connected that implies u and w are connected.
- By ordered pair problem means that (u,v) is different from (v,u).
- By Degree of a Server, problem means the number of bidirectional wires connected to it.
- It can be proven that you can always connect N servers with N-1 wires
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a two integers N and C denoting the number of servers and length of each wire.
For each test case, output a single line containing the maximum cost possible.
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 500
- 1 ≤ C ≤ 1000
Input: 1 2 1 Output: 3
|Time Limit:||5 sec|
|Source Limit:||3000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.