hdu 1875通畅工程再续-prim最小生成树
hdu 1875畅通工程再续-prim最小生成树
hdu 1875畅通工程再续
邻接矩阵中的数据必须初始化完整
#include<iostream> #include<math.h> using namespace std; const double INF=1000000000.0; double mp[100][100]; struct point { int x,y; } P[100]; double prim(int N) { int i,j,k,mark=1; double min,length; for(i=1;i<=N;i++) { mp[i][i]=0; //重要! mp[0][i]=mp[1][i]; } length=0; for(i=2;i<=N;i++) { min=INF; k=1; for(j=1;j<=N;j++) { if(mp[0][j]&&min>mp[0][j]) { min=mp[0][j]; k=j; } } if(k==1) return INF; length+=min; mp[0][k]=0; for(j=1;j<=N;j++) if(mp[0][j]&&mp[0][j]>mp[k][j]) mp[0][j]=mp[k][j]; } return length; } double dist(point x,point y) { return (double)sqrt((double)((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y))); } int main() { int i,j,T,N; double D,ans; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d%d",&P[i].x,&P[i].y); for(j=1;j<=i;j++) { D=dist(P[i],P[j]); if(10>D||1000<D) mp[i][j]=mp[j][i]=INF; else mp[i][j]=mp[j][i]=D; } } ans=prim(N); if(ans<INF) printf("%.1lf\n",100*ans); else printf("oh!\n"); } return 0; }