codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

444A.md (2785B)


      1 Source: https://codeforces.com/problemset/problem/444/A
      2 
      3 A. DZY Loves Physics
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 DZY loves Physics, and he enjoys calculating density.
     22 
     23 Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows:
     24 
     25 ![](https://espresso.codeforces.com/ddc049109c41af6c53df4e3447546ae396059ce4.png) where *v* is the sum of the values of the nodes, *e* is the sum of the values of the edges.
     26 
     27 Once DZY got a graph *G*, now he wants to find a connected induced subgraph *G*' of the graph, such that the density of *G*' is as large as possible.
     28 
     29 An induced subgraph *G*'(*V*', *E*') of a graph *G*(*V*, *E*) is a graph that satisfies:
     30 
     31 * ![](https://espresso.codeforces.com/46e20b4dfc895713f2da511b00037f3b583b7786.png);
     32 * edge ![](https://espresso.codeforces.com/3323e65c2bb0e7b15e71bc8acf5bbdd103bbd406.png) if and only if ![](https://espresso.codeforces.com/ff784919ccab7c1de161efd8c454dd842ca9a194.png), and edge ![](https://espresso.codeforces.com/5bd600027111301384bc3bf759bd32d812f393dd.png);
     33 * the value of an edge in *G*' is the same as the value of the corresponding edge in *G*, so as the value of a node.
     34 
     35 Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected.
     36 
     37  ![](https://espresso.codeforces.com/1252c805e97e9fa5fc53301fd7c5c88f2bc08313.png)
     38 
     39 Input
     40 
     41 The first line contains two space-separated integers *n* (1 ≤ *n* ≤ 500), ![](https://espresso.codeforces.com/bed2d5acbcccaf59b2f85a26a90ab00d2b92e1c4.png). Integer *n* represents the number of nodes of the graph *G*, *m* represents the number of edges.
     42 
     43 The second line contains *n* space-separated integers *x**i* (1 ≤ *x**i* ≤ 106), where *x**i* represents the value of the *i*-th node. Consider the graph nodes are numbered from 1 to *n*.
     44 
     45 Each of the next *m* lines contains three space-separated integers *a**i*, *b**i*, *c**i* (1 ≤ *a**i* < *b**i* ≤ *n*; 1 ≤ *c**i* ≤ 103), denoting an edge between node *a**i* and *b**i* with value *c**i*. The graph won't contain multiple edges.
     46 
     47 Output
     48 
     49 Output a real number denoting the answer, with an absolute or relative error of at most 10- 9.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 1 0  
     57 1
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 0.000000000000000
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 2 1  
     70 1 2  
     71 1 2 1
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 3.000000000000000
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 5 6  
     84 13 56 73 98 17  
     85 1 2 56  
     86 1 3 29  
     87 1 4 42  
     88 2 3 95  
     89 2 4 88  
     90 3 4 63
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 2.965517241379311
     97 ```
     98 
     99 Note
    100 
    101 In the first sample, you can only choose an empty subgraph, or the subgraph containing only node 1.
    102 
    103 In the second sample, choosing the whole graph is optimal.