1991483 2006-08-01 22:46:34 Accepted 1203 C++ 00:00.01 480K St.Crux O(n^3)。用邻接矩阵做的。什么？prim是什么......求最小生成树。不过我总觉得这个算法有待提高...... 另：double必须要用%lf来读入 #include <cstdio>#include <string>#include <cmath> double a[100][100], sum, p[100][2]; int b[100], n; void prim(){ int i, k, j, sp, ep; sum = 0; for(i = 1; i < n; i ++) {  double min = 30000;  for(k = 0; k < n; k ++) // 起点边  {   if(!b[k]) continue;   for(j = 0; j < n; j ++) // 终点边   {    if(b[j]) continue;    if(a[k][j] < min)    {     min = a[k][j];     sp = k, ep = j;    }   }  }  sum += min;  b[ep] = 1; }} void init(){ int i, k; memset(b, 0, sizeof(b)); b[0] = 1; for(i = 0; i < n; i ++) {  for(k = 0; k < n; k ++)  {   if(i == k) a[i][k] = 30000;   else   {    a[i][k] = sqrt((p[i][0] - p[k][0]) * (p[i][0] - p[k][0]) + (p[i][1] - p[k][1]) * (p[i][1] - p[k][1]));   }  } }} int main(){ freopen("in.txt", "r", stdin); int c = 0; while(scanf("%d ", &n) && n) {  if(c ++) printf("\n");  printf("Case #%d:\n", c);  int i;  for(i = 0; i < n; i ++)  {   scanf("%lf%lf", &p[i][0], &p[i][1]);  }  init();  prim();  printf("The minimal distance is: %0.2f\n", sum); } return 0;}

评论