题目大意：有N个点，M条有向边。
如今要求你以1为根。构造出一棵最小生成树，问这棵最小生成树是否能被构造出来，假设能够。总权值是多少
解题思路：朱刘算法的裸题。我仅仅想吐槽一下POJ，用的是double型的，输出时是%.2lf，结果是WA
换成了%.2f就A了。。这什么情况，白白花费了1个多小时去调错。。
#include#include #include using namespace std;#define N 110#define M 10010#define esp 1e-5const double INF = 1e9;struct Node { int x, y;}node[N];struct Edge{ int from, to; double dis;}E[M];int n, m, tot;int pre[N], id[N], vis[N];double in[N];double distance(int u, int v) { int x = node[u].x - node[v].x; int y = node[u].y - node[v].y; return sqrt(1.0 * x * x + 1.0 * y * y);}void AddEdge(int u, int v) { E[tot].from = u; E[tot].to = v; E[tot].dis = distance(u, v); tot++;}void init() { for (int i = 0; i < n; i++) scanf("%d%d", &node[i].x, &node[i].y); tot = 0; int u, v; for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); u--; v--; AddEdge(u, v); }}double ans;bool Directed_MST(int root) { ans = 0; int u, v, tmp; while (1) { for (int i = 0; i < n; i++) in[i] = INF; for (int i = 0; i < m; i++) { u = E[i].from; v = E[i].to; if (u != v && E[i].dis - in[v] < esp) { in[v] = E[i].dis; pre[v] = u; } } for (int i = 0; i < n; i++) { if (i == root) continue; if (in[i] == INF) return false; } int subnode = 0; memset(vis, -1, sizeof(vis)); memset(id, -1, sizeof(id)); in[root] = 0; for (int i = 0; i < n; i++) { ans += in[i]; tmp = i; while (vis[tmp] != i && id[tmp] == -1 && tmp != root) { vis[tmp] = i; tmp = pre[tmp]; } if (tmp != root && id[tmp] == -1) { u = pre[tmp]; while (u != tmp) { id[u] = subnode; u = pre[u]; } id[tmp] = subnode++; } } if (subnode == 0) return true; for (int i = 0; i < n; i++) if (id[i] == -1) id[i] = subnode++; for (int i = 0; i < m; i++) { tmp = E[i].to; E[i].from = id[E[i].from]; E[i].to = id[E[i].to]; if (E[i].from != E[i].to) E[i].dis -= in[tmp]; } root = id[root]; n = subnode; }}void solve() { if (!Directed_MST(0)) { printf("poor snoopy\n"); } else printf("%.2f\n", ans);}int main() { while (~scanf("%d%d", &n, &m)) { init(); solve(); } return 0;}