cho.shresearchmini
ProblemCode
Description
Time limit
Memory limit
cho.shTime limit
Memory limit
In the year 2100, Minsik lives in Antarctica. There are N villages, and some pairs of villages are connected by narrow one-way roads.
The installation cost of a police station is given for each village. Police stations do not have to be installed in every village. The condition is that every village must be reachable by following roads from at least one village that has a police station.
The president wants to satisfy this condition while making the average installation cost of the chosen police stations as small as possible.
Given the installation costs and the road information, compute the minimum possible average cost.
The first line contains the number of villages N. N is a positive integer not greater than 50.
The second line contains the installation costs for villages 0 through N-1. Each cost is a positive integer not greater than 1000.
The next N lines contain the road information as an adjacency matrix. In the row for village i, the j-th character is Y if there is a road from i to j, and N otherwise. There is no road from a village to itself.
Print the answer on the first line. An absolute or relative error up to 10^-9 is accepted.