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.

题意概述

给定平面上的$N$个点，其中$M$对点$(u_i, v_i)$之间可以连一条从$u_i$到$v_i$的有向边。要求使得从$1$号点出发可以到达其他所有点，求边的长度之和的最小值。

数据范围：$1 \le N \le 100, \ 1 \le M \le 10000$。

算法分析

最小树形图模板题。主要思想是先给对于每个点选一条最近的邻边，若没有形成环则退出，否则将环缩成一个点，重复以上步骤。

代码

#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;
}