# Command Network

## 题目描述

After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.

With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node $A$ to another node $B$, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.

## 代码

#include <cmath>
#include <cstdio>
#include <cstring>

static const int N = 1000;

int n, m, pre[N], id[N], vis[N];
double in[N];

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
double operator ! () const {
return sqrt(x * x + y * y);
}
} p[N];

struct Line {
int u, v; double w;
} l[N * N];

double calc(int root, int v, int e) {
double ret = 0;
while (1) {
for (int i = 0; i < v; ++ i) in[i] = 1e10;
for (int i = 0; i < e; ++ i)
if (l[i].w < in[l[i].v] && l[i].u != l[i].v)
pre[l[i].v] = l[i].u, in[l[i].v] = l[i].w;
for (int i = 0; i < v; ++ i)
if (i != root && in[i] == 1e10) return -1;
int cnt = 0; in[root] = 0;
memset(id, -1, sizeof id), memset(vis, -1, sizeof vis);
for (int i = 0; i < v; ++ i) {
ret += in[i]; int p = i;
while (vis[p] != i && ! ~ id[p] && p != root) vis[p] = i, p = pre[p];
if (p != root && ! ~ id[p]) {
for (int q = pre[p]; q != p; q = pre[q]) id[q] = cnt;
id[p] = cnt ++;
}
}
if (! cnt) break;
for (int i = 0; i < v; ++ i) if (! ~ id[i]) id[i] = cnt ++;
for (int i = 0; i < e; ++ i) {
if (id[l[i].u] != id[l[i].v]) l[i].w -= in[l[i].v];
l[i].u = id[l[i].u], l[i].v = id[l[i].v];
}
v = cnt, root = id[root];
}
return ret;
}

int main() {
while (~ scanf("%d%d", &n, &m)) {
for (int i = 0; i < n; ++ i) scanf("%lf%lf", &p[i].x, &p[i].y);
for (int i = 0; i < m; ++ i) {
scanf("%d%d", &l[i].u, &l[i].v), -- l[i].u, -- l[i].v;
if (l[i].u != l[i].v) l[i].w = ! (p[l[i].u] - p[l[i].v]); else l[i].w = 1e10;
}
double ans = calc(0, n, m);
if (ans == -1) printf("poor snoopy\n");
else printf("%.2lf\n", ans);
}
return 0;
} 418 I'm a teapot