zoj 1406 Jungle Roads 最小生成树-白红宇

zoj 1406 Jungle Roads 最小生成树

阅读量：2222 次

发布时间：2019-05-08

本文共 1715 字，大约阅读时间需要 5 分钟。

伸个懒腰，哈哈，第一个最小生成树写出来了！！！！虽然昨天刚刚写了并查集，但今天脑袋就是打不过来那个弯了，索性就用了标志数组，第一次试调的时候程序出了bug，然后一步一步分析，几乎重头到尾分析透了，终于找出bug了，一开始第58行是这样的

if(tag[u]!=tag[v])            {                sum+=node[i].w;                k++;                    for(j=0;j

由于本题中我把村庄初始化为0~n-1；并且标志数组初始化为村庄，所以在样例数据中取第三条边12时，合并过程出现bug，所以改成这样

if(tag[u]!=tag[v])            {                t1=tag[v];                sum+=node[i].w;                k++;                    for(j=0;j

嗯，下一步，要继续解决最小生成树问题，并尝试结合并查集来做，加油

#include
   
    typedef struct xx{    int vex1,vex2;    int w;}xxx;void  change(int *x,int *y){    int t;   t=*x;   *x=*y;   *y=t;}int main(){    int p,n,i,j,k,t1,t2,v,u,tag[27],sum;    char x1,x2;    xxx node[10000];    while(scanf("%d",&n)&&n)    {        p=0;        sum=0;         for(i=0;i
    
     node[j].w)                    k=j;                                         if(k!=i)           {                change(&node[i].vex1,&node[k].vex1);  //按边的权值排序                 change(&node[i].vex2,&node[k].vex2);                change(&node[i].w,&node[k].w);            }        }             for(i=0;i

看来看去，总感觉写的不好，虽然AC了，但是，和我最近看的Kruskal算法好像都不沾边，一定要解决Kruskal，这道题，之后又和媛姐代码对比了一下，很是惭愧，把媛姐的放在这做模板，还有3道最小生成树的题目，Kruskal和Prim都要自己解决，加油

#include 
   
      #include 
    
       #define N 28  #define MAXN 3000  int n,p,pre[N];  struct node  {      int x,y;      int len;  }city[MAXN];  typedef struct node NODE;  void input()  {      char from,to;      int num,i,j,len,a,b;      getchar();      p = 0;      for(i=1; i
     
      len > ((NODE*)b)->len ? 1 : -1;  }  int find( int x )  {      while( x!= pre[x] )          x = pre[x];      return x;  }  void kruskal()  {      int i,a,b,sum = 0;         qsort(city,p,sizeof(NODE),cmp);      for(i=0; i

你可能感兴趣的文章