给n个点坐标，其中某些点已经相连了
求一个最小生成树，输出还需相连的边的俩端点，所以得记录一下路径
这种输出边的题其实用kruskal算法应该能更简洁一些的
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int n,vis[755],pre[755],x[755],y[755],d[755],e[755][755]; void prim() { int i,j,p,tmp; memset(vis,0,sizeof vis); for(i=2;i<=n;i++) { pre[i]=1;//记录上一个经过的点 d[i]=e[1][i]; } d[1]=0;vis[1]=1; for(i=2;i<=n;i++) { tmp=inf;p=0; for(j=1;j<=n;j++) { if(!vis[j]&&tmp>d[j]) { tmp=d[j]; p=j; } } if(tmp!=0) printf("%d %d\n",pre[p],p); if(tmp==inf) break; vis[p]=1; for(j=1;j<=n;j++) { if(!vis[j]&&d[j]>e[p][j]) { d[j]=e[p][j]; pre[j]=p; } } } } int main() { int i,j,a,b,q; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { if(i==j) e[i][j]=0;//具体距离的值对判断大小不影响 所以下面也可以不取根号 else e[i][j]=e[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); } } scanf("%d",&q); while(q--) { scanf("%d%d",&a,&b);//已经相连的边直接使边权为0 e[a][b]=e[b][a]=0; } prim(); return 0; }