zhxfl+最小树形图.doc

zhxfl最小树形图#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;//记记和记果数boolvisit[110],circle[110];//visit记记记点有有被记记记~没circle记记改点是不是在一圈里个intn,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;}//圈记程~最后返回记是圈中的一点找个return-1;//如果有圈~返回没-1}voidupdate(intt)//记圈之后更新据数{inti;intj;ans+=graph[pre[t]][t];for(i=pre[t];i!=t;i=pre[i]){ans+=graph[pre[i]][i];circle[i]=true;}//首先把圈里的记记全部加起~且留出来并t记点~作记外部接口for(i=1;i<=n;++i)if(!circle[i]&&graph[i][t]!=INF)graph[i][t]-=graph[pre[t]][t];//上面记个for循记的作用是记t记点做更新操作~记什记要记做,可以