2017暑假训练第四天

时间:2022-07-20 20:25:51

  今天上午复习了一下图论中最小生成树和并查集有关的题目,做了练习中两个关于最小生成树的题目,两个题目都是标准的模板题,第一个题目顺利通过,但第二个题由于cin的速度过慢,所以一开始并未顺利ac,究于是否是算法出了问题,我又用prim算法敲了一次,结果也是未ac,最终换成scanf之后两个代码均顺利ac。虽然浪费了大量的时间,但对于代码的模板起到了一定的熟悉作用,下面总结一下两种算法:

  对于prim算法:

  这个算法的思路有点贪心的意味,大致思路是以一个点为起点,这个点所能到达的点进行一次检索,然后取路径权值最小的一个点为下一个点进行更新,一共更新n次,找到n个点,然后权值相加就是最小生成树的最小路径值和。

  这种算法的模板是:

  需要三个数组:

  int minn[101];//储存到达的最小边权

  bool fun[101];//储存是否访问过这个点

  int a[101][101];//储存边权(从i到j)

  memset (fun,0,sizeof(fun);

  memset (minn,0x7f,sizeof(minn);//把初始边权变为一个很大的数字

  minn[1]=0;//以1为起点开始查找

  for (i=1;i<=n;i++){

      x=0;

     for (j=1;j<=n;j++){

       if (!fun[j]&&minn[j]<minn[x]){//找下一个边权较小的点

            x=j;

       }

    }

    fun[x]=1;//标记x为下一个起点

    for (j=1;j<=n;j++){

        if (!fun[j]&&minn[j]<a[x][j]){//更新可到达的边权为最小值

             minn[j]=a[x][j];

        }

    }

  }

  这段代码结束后,minn中储存的便是最小生成树的所有边的边权。

  对于涉及到并查集查找方案kusckal算法,则是利用贪心和合并的原理,每次找边权最小的边,看看该边连接的两个点是否属于同一个“祖宗”,也就是是否已经连通,如果是,则进行下一次查找,如果不是,则合并两个边,边权加入总的边权中。一共寻找n-1次,得到一个最小生成树。

  这种算法的模板是:

  struct point {

   int s;

   int e;

   int v;

  }p[9901];//用结构体存边

  fa[101];//用数组存放每个点的“祖宗”

  int father(int x){

   if (fa[x]!=x)fa[x]=father(fa[x]);

   return fa[x];

 }//并查集专用找“祖宗”代码。。。

 void together(int x,int y){

  int f1=father(x);

  int f2=father(y);

  if (f1!=f2){

    fa[f1]=f2;

  }//"祖宗"的合并,表示其二者属于同一个连通区域

  sort(p+1,p+m+1,cmp);

  for (i=1,x=0;i<=m;i++){

   if (father(p[i].x)!=father(p[i].y)){

       together(p[i].x,p[i].y); 

      total+=p[i].v;

      x++;

   }  

   if (x==n-1)break;

  }

  算法结束后total存的便是最小生成树的最小路径边权和。

  下午的比赛做的有些迷迷糊糊,近几日光做搜索了,导致一见到题就想搜,结果理解错了题意,最后理解题意之后快速ac,虽然ac了,可还是浪费了大量的时间在一个假的题意上,可见快不是做题的目的, 理解了比什么都快。

  明天的训练决定开始对最短路径算法的复习,然后悉数开始做图论的题。