题目链接：http://poj.org/problem?id=3164
题意：第一行为n, m，接下来n行为n个点的二维坐标, 再接下来m行每行输入两个数u, v，表点u到点v是单向可达的，求这个有向图的最小生成树即求最小树形图；
思路: 这是一道最小树形图模板题；
我们可以用朱刘算法来解：
朱刘算法只有3步，然后不断循环。
1：找到每个点的最小入边。既然是生成树，那么对于每个点来说，只要选一个权值最小的入边就可以了。
贪心思想。因为如果不是最小入边，那么它肯定不是最小树形图的一条边，考虑它是没有意义的。
2：找环。找环找的是最小入边构成的新图的环。如果没找到环，那么一棵树就已经形成了，
因为树就是没有环的图。再因为边权都是最小的，因此此时最小树形图就已经出来了，停止循环。
3：如果第2步中找到了环，那么这个环就可以缩成一个点。然后构造新图，更新边权。更新边权的方法是：
假设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u, i, w)，在新图中连接(new, i, w)的边，其中new为新加的人工顶点;对于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。之所以是w-in[u]的原因是如果选择了w，那么那个in[u]在树中就是多余的，完全可以删除，所以需要减去，然后再后面的总费用累加中会体现出删掉了这个权值，不理解的画个图就明白了。
代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <string.h> 5 #include <algorithm> 6 #include <iomanip> 7 #define MAXN 210 8 using namespace std; 9 10 const int inf=0x3f3f3f3f; 11 struct node{ 12 int u, v; 13 double w; //**u到v的单向距离 14 }edge[MAXN*100]; 15 16 struct Point{ //**记录每个点的坐标 17 double x, y; 18 }point[MAXN]; 19 20 double in_dist[MAXN]; //记录i点的最短入边距离 21 int pre[MAXN]; //**记录i节点的前继节点 22 int id[MAXN]; //**记录新图点节点 23 int vis[MAXN]; //**判环 24 int k=1; //k为非自环边的数目 25 26 double dist(Point a, Point b){ 27 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 28 } 29 30 void add(int u, int v, double dist){ //***加边 31 edge[k].u=u; 32 edge[k].v=v; 33 edge[k++].w=dist; 34 } 35 36 double zhuliu(int root, int n){ 37 double ans=0; 38 while(true){ 39 for(int i=1; i<=n; i++){ 40 in_dist[i]=inf; 41 } 42 for(int i=1; i<k; i++){ //***找点i的最小入边 43 int u=edge[i].u; 44 int v=edge[i].v; 45 double w=edge[i].w; 46 if(u!=v&&in_dist[v]>w){//**注意这里新图也可能出现自环的情况，若不加u!=v的话会tle 47 in_dist[v]=w; 48 pre[v]=u; //**记录v的前继节点 49 } 50 } 51 for(int i=1; i<=n; i++){ 52 if(i==root){ 53 continue; 54 } 55 ans+=in_dist[i]; 56 if(in_dist[i]>=inf){ 57 return -1; //***根节点外还有孤立点，不存在最小树形图 58 } 59 } 60 memset(id, -1, sizeof(id)); 61 memset(vis, -1, sizeof(vis)); 62 int cnt=0; 63 for(int i=1; i<=n; i++){//***枚举每个点，找环 64 int v=i; 65 while(v!=root&&vis[v]!=i&&id[v]==-1){//**上溯父节点找环 66 vis[v]=i; 67 v=pre[v]; 68 } 69 if(v!=root&&id[v]==-1){ //***找到了环，缩点并且从新编号 70 ++cnt; 71 id[v]=cnt; 72 for(int u=pre[v]; u!=v; u=pre[u]){ 73 id[u]=cnt; 74 } 75 } 76 } 77 if(!cnt){ //***没有出现环 78 break; 79 } 80 for(int i=1; i<=n; i++){//***将余下的不在环中的点也重新编号 81 if(id[i]==-1){ 82 id[i]=++cnt; 83 } 84 } 85 for(int i=1; i<k; i++){//***建新图 86 int u=edge[i].u; 87 int v=edge[i].v; 88 edge[i].u=id[u]; 89 edge[i].v=id[v]; 90 if(edge[i].u!=edge[i].v){ 91 edge[i].w-=in_dist[v]; 92 } 93 } 94 n=cnt; //**更新节点数目 95 root=id[root]; //**更新根节点编号 96 } 97 return ans; 98 } 99 100 int main(void){ 101 // freopen("test.in", "r", stdin); 102 // freopen("test.out", "w", stdout); 103 int u, v, n, m; 104 while(~scanf("%d%d", &n, &m)){ 105 k=1; 106 for(int i=1; i<=n; i++){ 107 scanf("%lf%lf", &point[i].x, &point[i].y); 108 } 109 while(m--){ 110 scanf("%d%d", &u, &v); 111 if(u!=v){ //***删除自环 112 add(u, v, dist(point[u], point[v])); 113 } 114 } 115 int root=1; //**本题中没有指定根节点，任取一个即可 116 double ans=zhuliu(root, n); 117 if(ans==-1){ 118 puts("poor snoopy"); 119 }else{ 120 printf("%.2f ", ans); //**poj输出用lf会wa╭(╯^╰)╮ 121 } 122 } 123 return 0; 124 }