图论填个小坑。以前就一直在想，无向图有最小生成树，那么有向图是不是也有最小生成树呢，想不到还真的有，叫做最小树形图，网上的介绍有很多，感觉下面这个博客介绍的靠谱点：
http://www.cnblogs.com/vongang/archive/2012/07/18/2596851.html
所以下面的代码也是抄上面的模板的。里面还给出了不定根情况下的最小树形图的做法，新增一个虚拟根，连向其它所有点的费用是总费用＋1，然后跑一次算法就可以了，这样可以保证虚拟根一定连出去某个顶点，而且不可能连两个，最后跑出来把多的费用减掉就可以了。感觉想法挺神奇的。
#pragma warning(disable:4996)#include#include #include #include #include #include #include using namespace std;#define maxn 120#define maxm 12000int n, m;struct Edge{ int u, v; double w; Edge(int ui, int vi, double wi) :u(ui), v(vi), w(wi){} Edge(){}};vector E;double x[maxn], y[maxn];double dist(int i, int j){ return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));}double in[maxn]; // minimum pre edge weightint pre[maxn]; // pre vertexint vis[maxn]; // vis arrayint id[maxn]; // mark down the idint nv; // nv is the number of vertex after shrinkingdouble directed_mst(int root){ double ret = 0; int nv = n; while (1){ for (int i = 0; i < nv; ++i) in[i] = 1e10; for (int i = 0; i < m; ++i){ int u = E[i].u, v = E[i].v; if (E[i].w < in[v] && u != v){ in[v] = E[i].w; pre[v] = u; } } // found not connected means impossible for (int i = 0; i < nv; ++i){ if (i == root) continue; if (in[i]>1e9) return -1; } int cnt = 0; memset(id, -1, sizeof(id)); memset(vis, -1, sizeof(vis)); in[root] = 0; for (int i = 0; i < nv; ++i){ ret += in[i]; int v = i; while (vis[v] != i&&id[v] == -1 && v != root){ vis[v] = i; v = pre[v]; } // v!=root means we find a circle,id[v]==-1 guarantee that it's not shrinked. if (v != root&&id[v] == -1){ for (int u = pre[v]; u != v; u = pre[u]){ id[u] = cnt; } id[v] = cnt++; } } if (cnt == 0) break; for (int i = 0; i < nv; ++i){ if (id[i] == -1) id[i] = cnt++; } // change the cost of edge for each (u,v,w)->(u,v,w-in[v]) for (int i = 0; i < m; ++i){ int v = E[i].v; E[i].u = id[E[i].u]; E[i].v = id[E[i].v]; if (E[i].u != E[i].v) E[i].w -= in[v]; } // mark down the new root root = id[root]; // mark down the new vertex number nv = cnt; } return ret;}int main(){ while (cin >> n >> m){ E.clear(); for (int i = 0; i < n; ++i){ scanf("%lf%lf", x + i, y + i); } int ui, vi; for (int i = 0; i < m; ++i){ scanf("%d%d", &ui, &vi); --ui; --vi; if (ui != vi) E.push_back(Edge(ui, vi, dist(ui,vi))); } m = E.size(); double ans = directed_mst(0); if (ans < 0) puts("poor snoopy"); else printf("%.2f\n", ans); } return 0;}