题目来源：POJ 3164 Command Network

题意：求以1为根的最小树形图 没有输出字符串

思路：直接高朱刘算法 不懂的可以百度 学会了就是直接套模板的事情 其实就是不断消圈而已 不构成圈就有解 无法从根到达其他点就无解

#include <cstdio>#include <cstring>#include <cmath>const int maxn = 110;const int maxm = 50010;const double INF = 999999999;struct edge{	int u, v;	double w;	edge(){}	edge(int u, int v, double w) : u(u), v(v), w(w){}}e[maxm];struct Point{	double x, y;}p[maxn];int pre[maxn], vis[maxn], no[maxn];double in[maxn];double dis(Point a, Point b)  {      return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));  }  double MST(int n, int m, int rt){	double ans = 0;	while(1)	{		for(int i = 1; i <= n; i++)			in[i] = INF;		for(int i = 1; i <= m; i++)		{			int u = e[i].u;			int v = e[i].v;			if(u != v && in[v] > e[i].w)			{				pre[v] = u;				in[v] = e[i].w;			}		}		for(int i = 1; i <= n; i++)		{			if(i == rt)				continue;			if(in[i] == INF)				return -1;		}		memset(no, -1, sizeof(no));		memset(vis, -1, sizeof(vis));		in[rt] = 0;		int cnt = 0;		for(int i = 1; i <= n; i++)		{			ans += in[i];			int v = i;			while(v != rt && vis[v] != i && no[v] == -1)			{				vis[v] = i;				v = pre[v];			}			if(v != rt && no[v] == -1)			{				for(int u = pre[v]; u != v; u = pre[u])					no[u] = cnt+1;				no[v] = cnt+1;				cnt++;			}		}		if(!cnt)			return ans;		for(int i = 1; i <= n; i++)			if(no[i] == -1)				no[i] = ++cnt;		for(int i = 1; i <= m; i++)		{			int u = e[i].u;			int v = e[i].v;			e[i].u = no[u];			e[i].v = no[v];			if(no[u] != no[v])			{				e[i].w -= in[v];			}		}		n = cnt;		rt = no[rt];	}	return ans;}int main(){	int n, m;	while(scanf("%d %d", &n, &m) != EOF)	{		for(int i = 1 ; i <= n; i++)			scanf("%lf %lf", &p[i].x, &p[i].y);		int add = 1;		for(int i = 1; i <= m; i++)		{			scanf("%d %d", &e[add].u, &e[add].v);			if(e[add].u == e[add].v)				continue;			e[add].w = dis(p[e[add].u], p[e[add].v]);			add++;		}		double ans = MST(n, add-1, 1);		if(ans < 0)			puts("poor snoopy");		else			printf("%.2f\n", ans);	}	return 0;}