本题是 最小生成树，用prim 比较方便，用kruskal的话，我超时了，看了discuss 后才知道要用优先队列 优化。而且这题 prim 效率应该效率更高。 kruskal +优先队列 Memory: 8032K Time: 125MS Language: C++ Result: Accepted #include<iostream>#include<cmath>#include<algorithm>using namespace std;int N,M,set[1021],need,num;double vx[1001],vy[1001];struct edge{ int x,y; double w;}e[555555];int find (int x){ int i,j,r; r=x; while(set[r]!=r) r=set[r]; j=x; while(j!=r) { i=set[j]; set[j]=r; j=i; } return r;}void merge(int x,int y){ if(x>y) set[x]=y; else set[y]=x;}void insert(edge a){ int i; num++; e[num]=a; i=num; while(i>1 && e[i].w<e[i/2].w) { swap(e[i],e[i/2]); i=i/2; }}void heapify(int i){ int l,r,small; l=i*2;; r=l+1; small=i; if(l<=num && e[small].w>e[l].w) small=l; if(r<=num && e[small].w>e[r].w) small=r; if(i!=small) { swap(e[i],e[small]); heapify(small); }}edge del(){ edge min; min=e[1]; swap(e[1],e[num]); num--; heapify(1); return min;} double dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double kruskal(){ int sn,sm; double sum=0; edge temp; for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) { sn=find(i); sm=find(j); if(sn!=sm) { temp.x=i; temp.y=j; temp.w=dis(vx[i],vy[i],vx[j],vy[j]); insert(temp); } } for(int i=1;i<=num;i++) { temp=del(); sn=find(temp.x); sm=find(temp.y); if(sn!=sm) { merge(sn,sm); sum+=temp.w; need--; } if(need==0)break; } return sum;}int main(){ int n,m,count; double total; while(scanf("%d%d",&N,&M) !=EOF) { count=0; for(int i=1;i<=N;i++) { scanf("%lf%lf",&vx[i],&vy[i]); } for(int i=1;i<=N;i++) set[i]=i; for(int i=1;i<=M;i++) { int sn,sm; scanf("%d%d",&n,&m); sn=find(n); sm=find(m); merge(sn,sm); } need=-1; for(int i=1;i<=N;i++) { if(set[i]==i )need++; } total=kruskal(); printf("%.2lf\n",total); num=0; }} 直接prim算法 Memory: 8052K Time: 94MS Language: C++ Result: Accepted #include<iostream>#include<cmath>using namespace std;double map[1001][1001];int N,M;double prim(){ bool vis[1001]={0}; double lw[1001],min,sum; int k; for(int i=1;i<=N;i++) lw[i]=map[1][i]; vis[1]=1; sum=0; for(int i=1;i<N;i++) { min=10000001; for(int j=1;j<=N;j++) if(!vis[j] && lw[j]<min) { min=lw[j]; k=j; } sum+=min; vis[k]=1; for(int j=1;j<=N;j++) if( !vis[j] && map[k][j]<lw[j]) lw[j]=map[k][j]; } return sum;}double dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int main(){ double vx[1001],vy[1001],total; int n,m; while(scanf("%d%d",&N,&M) !=EOF) { for(int i=1;i<=N;i++) scanf("%lf%lf",&vx[i],&vy[i]); for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) { double temp=dis(vx[i],vy[i],vx[j],vy[j]); map[i][j]=map[j][i]=temp; } for(int i=1;i<=M;i++) { scanf("%d%d",&n,&m); map[n][m]=map[m][n]=0; } total=prim(); printf("%.2lf\n",total); } }
评论