CSG-CPC
Online Judge

# 1257 : Energy Distribution

Time Limit: 1 Sec     Memory Limit: 256 Mb     Submitted: 44     Solved: 18     SpecialJudge

## Description

There are $$n$$ planets in the galaxy. Some undirected tunnels connect planets. There exists at most one tunnel connecting each pair of planets. So these tunnels can be described as an $$n\times n$$ matrix $$W_{n\times n}$$. Specifically, the tunnel connecting planet $$i$$ and $$j$$ has a width of $$w_{i,j}$$(If there is no tunnel between planet $$i$$ and $$j$$, then $$w_{i,j}=0$$).

Now, you want to distribute exactly $$1.0$$ unit of energy among the $$n$$ planets. Suppose that planet $$i$$ is distributed $$e_i$$(a real number) unit of energy ($$e_i\ge 0, \sum_{i=1}^ne_i=1$$), these planets will bring $$E$$ magical value, where $$E = \sum_{i=1}^n\sum_{j=i+1}^ne_ie_jw_{i,j}$$.

Please distribute the energy and maximize the magical value.

## Input

The first line contains an interger $$n(1\le n\le 10)$$.

For the next $$n$$ lines, each line contains $$n$$ intergers. The $$j$$-th integer in the $$i$$-th line is $$w_{i,j}(0\le w_{i,j}\le 1000)$$. Indicating the matrix $$W_{n\times n}$$.

## Output

Output a real number as the answer. If your answer is $$A$$ while the standard answer is $$B$$, your answer will be accepted if and only if $$\frac{|A-B|}{\max(|A|,1)} \le 10^{-6}$$.

## Sample

2
0 1
1 0
##CASE##
3
0 2 1
2 0 2
1 2 0
0.250000
##CASE##
0.571429

FUDAN