# Untitled

unknown
plain_text
17 days ago
2.8 kB
4
Indexable
Never
```public class abc {
static int n;
static int a, b, c;
static double matrix[][], key[];
static boolean visited[][], visit[];

public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
n = sc.nextInt();
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
visited = new boolean[n + 1][n + 1];
matrix = new double[n + 1][n + 1];
visit = new boolean[n + 1];
key = new double[n + 1];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
matrix[i][j] = sc.nextDouble();
if (i != j && !visited[i][j]) {
visited[i][j] = true;
matrix[i][j] = solve(matrix[i][j]);
}
}
}

for (int i = 1; i <= n; i++) {
key[i] = Double.MAX_VALUE;
}

prim();
double ans = 0.0;
for (int i = 1; i <= n; i++) {
ans += key[i];
}

System.out.printf("#%d %.3f\n", tc, ans);
}
sc.close();
}

static double solve(double value) {
double left = 0.0, right = value;
while (right - left > 1e-6) {
double mid = left + (right - left) / 2.0;
double num = a * Math.pow(mid, 3) + b * Math.pow(mid, 2) + c;
if (value == num) {
return mid;
} else if (value < num) {
right = mid;
} else {
left = mid;
}
}
return left;
}

static int findMin() {
double min = Double.MAX_VALUE;
int min_idx = 0;
for (int i = 1; i <= n; i++) {
if (!visit[i] && key[i] < min) {
min = key[i];
min_idx = i;
}
}
return min_idx;
}

static void prim() {
key[1] = 0;
for (int i = 1; i <= n - 1; i++) {
int u = findMin();

visit[u] = true;
for (int v = 1; v <= n; v++) {
if (!visit[v] && u != v && key[v] > matrix[u][v]) {
key[v] = matrix[u][v];
}
}
}
}
}

#1 6.000
#2 9.119
#3 8.060
#4 26.371
#5 18.983
#6 29.117
#7 18.328
#8 30.336
#9 22.253
#10 33.033
#11 11123563.825
#12 30373854.103
#13 7567499.915
#14 11797034.099
#15 8463058.600
#16 2439733.779
#17 16178946.582
#18 9403868.822
#19 6891839.275
#20 7824343.076
#21 8766828.461
#22 7565958.813
#23 6602238.269
#24 11277332.021
#25 4449955.050
#26 7952083.534
#27 3242380.583
#28 4534051.931
#29 2589291.416
#30 3826996.791
#31 3513981.974
#32 6257813.395
#33 7217559.068
#34 8888707.143
#35 5783796.235
#36 10532357.478
#37 5135140.983
#38 10406849.351
#39 4593651.588
#40 5006037.684
#41 15247286.743
#42 11474689.224
#43 8663165.338
#44 10914022.383
#45 7609414.126
#46 12268572.649
#47 14053342.152
#48 13705856.786
#49 10789210.075
#50 18318118.359```