学步园

/*<br /> Author: ACb0y<br /> Date: 2010-5-22<br /> Result: AC<br /> Descripition: UVa 10034 Freckles(mst)<br /> */</p> <p>#include <iostream><br /> #include <cmath><br /> using namespace std;</p> <p>double INF = 1 << 30;</p> <p>struct point {<br /> double x;<br /> double y;<br /> };</p> <p>double d[110];<br /> point ps[110];<br /> int vis[110];<br /> int n;</p> <p>double get_dis(int a, int b) {<br /> return sqrt((ps[a].x - ps[b].x) * (ps[a].x - ps[b].x) + (ps[a].y - ps[b].y) * (ps[a].y - ps[b].y));<br /> }</p> <p>double mst() {<br /> int i, j;<br /> for (i = 0; i < n; i++) {<br /> d[i] = INF;<br /> }<br /> d[0] = 0;<br /> double ans = 0;<br /> memset(vis, 0, sizeof(vis));<br /> for (i = 0; i < n; i++) {<br /> double min = INF;<br /> int pos;<br /> for (j = 0; j < n; j++) if (!vis[j]) {<br /> if (d[j] < min) {<br /> min = d[j];<br /> pos = j;<br /> }<br /> }<br /> ans += min;<br /> vis[pos] = 1;<br /> for (j = 0; j < n; j++) if (!vis[j]) {<br /> double temp = get_dis(pos, j);<br /> if (temp < d[j]) {<br /> d[j] = temp;<br /> }<br /> }<br /> }<br /> return ans;<br /> }</p> <p>int main() {<br /> #ifndef ONLINE_JUDGE<br /> freopen("10034.txt", "r", stdin);<br /> #endif<br /> int k;<br /> cin >> k;<br /> while (k--) {<br /> cin >> n;<br /> for (int i = 0; i < n; i++) {<br /> cin >> ps[i].x >> ps[i].y;<br /> }<br /> printf("%.2lf/n", mst());<br /> if (k != 0) {<br /> cout << endl;<br /> }<br /> }<br /> return 0;<br /> }