HDOJ 1875 畅通工程再续

这个畅通工程还是一交就过，看来畅通工程用来入门是最好了，以后拿这些来挂就不会那么打击人了，天天开心。这里求最小生成树之前要自己构图，很简单就是求出点到点之间的距离，如果距离大于1000和小于10都视作不连通。点少，还是Prim就好了。不过这里存在不连通的情况，不想前面的的工程那么畅通，最后加一个循环判断就好了。

#include<stdio.h>#include<math.h>#include<string.h>struct Point{       int x,y;} pt[105];double d[105],map[105][105];bool v[105];int c;double Dist(Point a,Point b){       return sqrt( (a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y) );}void Graph(){     int i,j;     double t;     memset(map,0,sizeof(map));     for( i=0; i<c-1; i++){          for( j=i+1; j<c; j++){               t=Dist(pt[i],pt[j]);               if( t>=10&&t<=1000){                   map[i][j]=t;                   map[j][i]=t;               }          }     }}double Prim(){    int i,j,pt;    double ret,mim;    memset(d,0,sizeof(d));    memset(v,false,sizeof(v));    pt=0;  v[0]=true;  ret=0;    while( true){           for( i=0; i<c; i++)                 if( !v[i]&&map[pt][i]&&(d[i]>map[pt][i]||d[i]==0) )                    d[i]=map[pt][i];             pt=-1; mim=10000;           for( i=0; i<c; i++){                if( !v[i]&&d[i]&&mim>d[i] ){                    mim=d[i];                    pt=i;                }           }                  v[pt]=true;           if( pt==-1) break;          ret+=mim;     }    for( i=0; i<c; i++)//判断是否联通         if( !v[i])             return -1;     return ret;}int main(){    int t,i;    double ret;    scanf("%d",&t);    while( t--){           scanf("%d",&c);           for( i=0; i<c; i++)                  scanf("%d%d",&pt[i].x,&pt[i].y);            Graph();           ret=Prim();           if( ret==-1)               printf("oh!\n");           else{                ret=ret*100;                printf("%.1lf\n",ret);           }    }    return 0;}