This is a template problem of minimum tree graph

At the beginning of Zhu Liu's algorithm, it wasn't easy to understand. I read a lot of articles on the Internet to understand it.

In this case, if the V-point of arc (u,v) is in a ring, and the number of the V-point formed by the ring is k in the new graph, then the weight of (u,k) in the new graph is W(u,v)-in[v], because ret (the final return value) is set to 0 only once at the beginning of Zhu Liu algorithm, and the change of the weight can ensure that when adding a new edge to a point, the last one can be added by the way The weight of the old edge is removed from RET, as is the case for points not on the ring

The code is as follows (the template comes from kuangbin)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 105
#define maxm 10005
using namespace std;
struct Edge
{
	int u, v;
	double cost;
};
Edge edge[maxm];
int pre[maxn], vis[maxn],id[maxn];
double in[maxn],xy[maxn][2];
inline double cal_dis(int i,int j)
{
	return sqrt(pow(xy[i][0] - xy[j][0], 2) + pow(xy[i][1] - xy[j][1], 2));
}
//Root is the serial number of the root, n is the number of points, and m is the number of effective edges (i.e. remove the self ring)
double liuzhu(int root, int n, int m)
{
	int v,tn;
	double ret = 0;
	while (1)
	{
		for (int i = 1; i <= n; i++)
			in[i] = -1;//-1 indicates that the edge does not exist
		for(int i=0;i<m;i++)
			if (edge[i].cost < in[edge[i].v]|| in[edge[i].v]<0)
			{
				in[edge[i].v] = edge[i].cost;
				pre[edge[i].v] = edge[i].u;
			}
		for (int i = 1; i <= n; i++)
			if (i != root && in[i]<0)
				return -1;
		tn = 0;
		in[root] = 0;
		memset(id, -1, sizeof(id));
		memset(vis, -1, sizeof(vis));
		for (int i = 1; i <= n; i++)
		{
			ret += in[i];
			v = i;
			while (vis[v] != i && id[v] == -1&&v!=root)
			{
				vis[v] = i;
				v = pre[v];
			}
			if (id[v] == -1 && v != root)
			{
				tn++;//The sequence number of points here starts from 1, so tn should be added first
				for (int u = pre[v]; u != v; u = pre[u])
					id[u] = tn;
				id[v] = tn;
			}
		}
		if (!tn) break;
		for (int i = 1; i <= n; i++)
			if (id[i] == -1)
				id[i] = ++tn;
		for (int i = 0; i < m;)
		{
			v = edge[i].v;
			edge[i].u = id[edge[i].u];
			edge[i].v = id[edge[i].v];
			if (edge[i].u != edge[i].v)
				edge[i++].cost -= in[v];
			else
				swap(edge[i], edge[--m]);//If it is an edge in the ring, discard the edge and set the total number of edges to - 1
		}
		n = tn;
		root = id[root];
	}
	return ret;
}
int main()
{
	int n, m, lcnt;
	double t;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++) scanf("%lf%lf", &xy[i][0], &xy[i][1]);
		lcnt = 0;//Used to count the number of valid arcs
		for (int i = 0,u,v; i < m; i++)
		{
			scanf("%d%d", &u, &v);
			if (u != v)
			{
				edge[lcnt].u = u;
				edge[lcnt].v = v;
				edge[lcnt++].cost = cal_dis(u, v);
			}
		}
		if (lcnt < n - 1) t = -1;//If the number of non self arcs is less than n-1, the tree graph cannot be formed
		else t = liuzhu(1, n, lcnt);
		if (t < 0) printf("poor snoopy\n");
		else printf("%.2lf\n", t);
	}
	return 0;
}