primchatnhiphandouble
quoc14
c_cpp
20 days ago
1.8 kB
2
Indexable
Never
caidat
#include <iostream> using namespace std; int n, a, b, c; double map[100][100]; int visit[100]; double ans; double abss(double x) { if (x > 0) return x; return -x; } double chatnhiphan(double k) { double lo = 0.0000000000000; double hi = 1000000000.00000000; while (lo < hi) { double mid = (lo + hi) / 2; if (abss(a * mid * mid * mid + b * mid * mid + c - k) < k * 0.0000000001) { return mid; } else if (a * mid * mid * mid + b * mid * mid + c > k) { hi = mid; } else { lo = mid; } } return lo; } void prim() { for (int i = 1; i <= n; i++) { visit[i] = 0; } visit[1] = 1; int count = 1; int jmini; while (count < n) { double mini = 1000000000.00000000; for (int i = 1; i <= n; i++) { if (visit[i] == 1) { for (int j = 1; j <= n; j++) { if (i != j && visit[j] == 0) { if (map[i][j] < mini) { mini = map[i][j]; jmini = j; } } } } } visit[jmini] = 1; ans += mini; //cout << mini << endl; count++; } } void solve(int testcase) { cin >> n >> a >> b >> c; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; } } for (int i = 1; i <= n - 1; i++) { for (int j = i + 1; j <= n; j++) { if (map[i][j] != 0) { map[i][j] = chatnhiphan(map[i][j]); map[j][i] = map[i][j]; } } } /* for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << map[i][j] << " "; } cout << endl; } */ ans = 0.0000000000; prim(); cout.setf(ios::fixed); cout.precision(3); cout << "#" << testcase << " " << ans << endl; } int main() { //freopen("Text.txt", "r", stdin); int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } return 0; }
Leave a Comment