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;elsemp[i][j]=mp[j][i]=D;}}ans=prim(N);if(ans<INF) printf("%.1lf\n",100*ans);else printf("oh!\n");}return 0;}