kruskal(2)-zoj-1203 - c++编程基础

这道题花了我n多时间,最关键的是我的时间不是花在算法上,而是其中一个小的临界值上.照着模板抄下来,途中打算自己写,结果就是找错找了一下午.这也就是看在在假期里时间比较宽松可以这样浪费,这样下去,可不是办法.
思路:在一个平面上n个点且两两相连,每边有权值,让你找出n-1个点形成无回路的连通图,当然是权值最小;题目给你的是n个城市的坐标,第一个为x坐标,第二个为y坐标,这与kruskal算法直接给出顶点数与边数还有权值有点变化,这可能就是编程的最大乐趣了!我先这样处理:取两个double数组X[],Y[],接下来将每个坐标的x,y分别写入,Then,double d=sqrt((xi-xj)^2+(yi-yj)^2),得到权值,在与各顶点封装排序.还有一点是计算d的时候,举个测例:由5个城市的坐标怎么得到其中1个城市与其他4个城市的距离与顶点表示
for(i=0;i {

for(j=i+1;j {
//scanf("%f%f",&x,&y);自己第一次写的
//两点之间的距离
d=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
edges[m].u=i;
edges[m].v=j;
edges[m].w=d;

m++;

}
}
这样,会出现
0-->1=d;
0-->2,
0-->3
...
我的关键在于kruskal算法的理解与应用上自己还有太大的差距,还有并查集.

最最关键:这道题没有通过

#include 
     
      
#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define MAXN 105 #define MAXM 5050 double X[MAXN],Y[MAXN];//用来存储x,y的坐标，其他关于坐标的运算可以模仿 int i,n,j,m,mi,x,y;//循环变量,frist i defined it in main() double sum=0.0;//总权值 struct edge { int u,v;//顶点 double w;//权值，注意类型 }edges[MAXN]; int parent[MAXN]; int cmp(const void *a,const void *b) { // return (*(edge *))我想用另种方法 edge aa=*(const edge *)a;edge bb=*(const edge *)b; if (aa.w>bb.w) return 1; else return -1; } void UFset()//初始化 { for(i=0;i<=mi;i++) parent[i]=-1; } int Find(int x)//查找并返回节点x所属集合的根节点 { int s=x; for(;parent[s]>=0;s=parent[s]) ; while(s!=x)//优化方案――压缩路径，使后续查找更加方便，但为什么呢 { parent[x]=s; x=s; } return s; } void Union(int R1,int R2) { int r1=Find(R1),r2=Find(R2);// r1,r2分别为根节点 int tmp=parent[r1]+parent[r2]; if(parent[r1]>parent[r2])//优化方案，路径加权 { parent[r1]=r2;parent[r2]=tmp; } else { parent[r2]=r1;parent[r1]=tmp; } } void kruskal() { int num=0; //int u,v; UFset(); for(i=0;i
          
           =n-1) break; } } int main() { // freopen("in.txt","r",stdin); // int n;//测试数据的个数 double d;//可以不要了 //int m=0,mi;//边的标志,中间变量 int kcase=1; while(1) { cin>>n; if(n==0) break; //输入各个城市的坐标 for(i=0;i
           
            %d=%0.2f\n",edges[i].u,edges[i].v,edges[i].w); if(kcase>1) cout<