zhxfl 最小树形图.docx

zhxfl 最小树形图.docx#include<iostream>#include<cstring>#include<cstdio>#include<cmath>usingnamespacestd;#defineINF99999999#definemin(a,b)((a)<(b)?(a):(b))structpoint{   doublex;   doubley;}p[200];intpre[200];//记录该节点的前驱doublegraph[200][200],ans;//图数组和结果bool  visit[110],circle[110];//visit记录该点有没有被访问过,circle记录改点是不是在一个圈里int   n,m,root;//顶点数+边数+根节点标号voiddfs(intt)//一个深度优先搜索,搜索出一个最大的联通空间{   inti;   visit[t]=true;   for(i=1;i<=n;++i)   {       if(!visit[i]&&graph[t][i]!=INF)           dfs(i);   }}boolcheck()//这个函数用来检查最小树形图是否存在,即如果存在,那么一遍dfs后,应该可以遍历到所有的节点{   memset(visit,false,sizeof(visit));   dfs(root);   for(inti=1;i<=n;++i)   {       if(!visit[i])           returnfalse;   }   returntrue;}doubledist(inti,intj){   returnsqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));}intexist_circle()//判断图中是不是存在有向圈{   inti;   intj;   root=1;pre[root]=root;   for(i=1;i<=n;++i)   {       if(!circle[i]&&i!=root)       {           pre[i]=i;graph[i][i]=INF;           for(j=1;j<=n;++j)           {               if(!circle[j]&&graph[j][i]<graph[pre[i]][i])//找出指向i最小的                   pre[i]=j;           }       }   }//这个for循环负责找出所有非根节点的前驱节点   for(i=1;i<=n;++i)   {       if(circle[i])           continue;       memset(visit,false,sizeof(visit));       intj=i;       while(!visit[j])       {           visit[j]=true;           j=pre[j];       }       if(j==root)           continue;       returnj;   }//找圈过程,最后返