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

模板,但我还不是很熟练…

在我理解来,最小树形图就是不断贪心的过程

每一轮都筛选出$n-1$条边

检查是否成环,不成环就是最小树形图

成环需要进行缩点…

#include 
   
    #include 
    
     #include 
     
       #include 
      
       using namespace std;const int maxn = 2e5+10;const int inf = 2e9;const double eps = 1e-7;struct edge{
   	int u,v; double w;}a[maxn];int vis[maxn],id[maxn],n,pre[maxn],top,m;double x[maxn],y[maxn],inw[maxn];double zhuliu(int root ){
   	double ans = 0;	while( 1 )	{
   		for(int i=1;i<=n;i++)	inw[i] = inf;		for(int i=1;i<=top;i++)		{
   			int v = a[i].v, u = a[i].u;			if( u!=v && inw[v]>a[i].w+eps )				inw[v] = a[i].w, pre[v] = u;		}		for(int i=1;i<=n;i++)			if( i!=root && inw[i]==inf )	return -1;		int cnt = 0;		for(int i=1;i<=n;i++)	vis[i] = id[i] = 0;		for(int i=1;i<=n;i++)		{
   			if( i==root )	continue;			int v = i;			ans += inw[i];			while( v!=root&&!id[v]&&vis[v]!=i )				vis[v] = i, v = pre[v];			if( !id[v] && v!=root )			{
   				id[v] = ++cnt;				for(int u = pre[v]; u!=v; u = pre[u] )	id[u] = cnt;			}		}		if( cnt == 0 )	break;		for(int i=1;i<=n;i++)			if( !id[i] )	id[i] = ++cnt;		for(int i=1;i<=top;i++)		{
   			int u = a[i].u, v = a[i].v;			a[i].u = id[u],a[i].v = id[v];			if( id[u]!=id[v] )	a[i].w-=inw[v];		}		root = id[root];		n = cnt;	}	return ans;}int main(){
   	while( scanf("%d%d",&n,&m) != EOF )	{
   		top = 0;		for(int i=1;i<=n;i++)			scanf("%lf%lf",&x[i],&y[i]);		for(int i=1;i<=m;i++)		{
   			int q,w; scanf("%d%d",&q,&w);			if( q!=w )			{
   				a[++top].u = q, a[top].v = w;				a[top].w = sqrt( (x[q]-x[w])*(x[q]-x[w])+(y[q]-y[w])*(y[q]-y[w]) );			}		}		double ans = zhuliu(1);		if( ans == -1 )	printf("poor snoopy\n");		else	printf("%.2f\n",ans);	}}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109579713 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！