本文主要是介绍10034 - Freckles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
求最小生成树，可用PRIM 也可用 KRUSKRAL 。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int father[110];
double x[110],y[110];
typedef struct{int st;int en;double dist;
}Node;
Node g[5100];int cmp(const void *a,const void *b){Node * _a = (Node *) a;Node * _b = (Node *) b;return _a->dist - _b->dist;
}int finds(int x){return father[x] = x ? x: finds(father[x]);
}int main(){int i,j;int t,n;int cnt;scanf("%d",&t);while(t--){scanf("%d",&n);for(i = 0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]);cnt = 0;for(i = 0;i<n;i++){for(j = i+1;j<n;j++) {g[cnt].st = i;g[cnt].en = j;g[cnt++].dist = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}}qsort(g,cnt,sizeof(g[0]),cmp);for(i = 0;i<n;i++) father[i] = i;double ans = 0;for(i = 0;i<cnt;i++){int fx = finds(g[i].st);int fy = finds(g[i].en);这里只给出 KRUSKRAL 的部分代码。望请谅解。
这篇关于10034 - Freckles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
