大意：
给出一些点，求MST
把这几天的MST一口气发上来。
kruskal
#includeprim#include #include using namespace std;const int MAXN=101;const int INF=9999999;int fa[MAXN];struct point{ double x,y;}ship[MAXN];struct dot{ int x,y; double dis;}dis[MAXN*MAXN];int find(int cur){ return fa[cur]==cur?cur:fa[cur]=find(fa[cur]);}bool operator < (const dot &a,const dot& b){ return a.dis
#include#include const int MAXN=101;const int INF=9999999;double map[MAXN][MAXN];double dis[MAXN];struct point{ double x,y;}ship[MAXN];void prim(int n){ for(int i=1;i<=n;i++) dis[i]=INF; bool vis[MAXN]={0}; int cur=1; vis[cur]=1; dis[cur]=0; int i,j; for(i=1;i<=n;i++) { double mini=INF; for(j=1;j<=n;j++) if(!vis[j] && dis[j] > map[cur][j]) dis[j]=map[cur][j]; for(j=1;j<=n;j++) if(!vis[j] && mini > dis[j]) mini=dis[cur=j]; vis[cur]=true; }}int main(){ int n,kase=1; while(~scanf("%d",&n),n) { if(kase!=1) printf("\n"); int i,j; for(i=1;i<=n;i++) scanf("%lf%lf",&ship[i].x,&ship[i].y); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j]= map[j][i] = sqrt((ship[j].y -ship[i].y) *(ship[j].y -ship[i].y) + (ship[j].x -ship[i].x)*(ship[j].x -ship[i].x)); } } prim(n); double ans=0,ans2=0;//=map[a][b]; for(i=1;i<=n;i++) ans+=dis[i]; printf("Case #%d:\n",kase++); printf("The minimal distance is: %.2lf\n",ans); }}