UVa 889 Islands

题目描述

给定 $N$ 个互不相交、不接触的岛屿（用多边形表示），需要用桥梁将所有岛屿间接连接起来（即构建一棵最小生成树），使得桥梁总长度最小。岛屿可近似为多边形，两岛屿之间的距离定义为它们边界上任意两点间的最短欧几里得距离（即两多边形之间的最短距离）。要求输出桥梁数量（$N-1$）和总长度，精确到三位小数。

输入格式

第一行为一个整数，表示测试用例个数。每个测试用例第一行为整数 $N$（$2\le N\le 100$），表示岛屿数量。随后 $N$ 行，每行描述一个岛屿：首先是一个整数 $P$（$1\le P\le 25$），表示多边形顶点数，随后 $P$ 对整数坐标 $(x_i,y_i)$，按顺序给出顶点（顺时针或逆时针），最后一个顶点与第一个顶点相连形成闭合多边形。坐标范围为 $[-1000,1000]$。岛屿不会相交或接触。各测试用例之间无空行。

输出格式

对于每个测试用例，输出一行，格式为：

The minimal interconnect consists of N-1 bridges with a total length of L

其中 $L$ 为最小总长度，保留三位小数。

样例输入

1
3
4 0 0 0 1 1 1 1 0
4 2 0 2 1 3 1 3 0
3 4 0 5 0 5 1

样例输出

The minimal interconnect consists of 2 bridges with a total length of 2.000

题目分析

问题等价于在岛屿之间建立最小生成树。节点为岛屿，边权为两岛屿多边形之间的最短距离。因此需要：

步骤 $\text{1}$. 计算任意两岛屿之间的最短距离。两多边形之间的最短距离等于它们所有边对之间最短距离的最小值。对于两条线段 $s_1$ 和 $s_2$，其最短距离为：

• 端点 $s_1.p_1$ 到 $s_2$ 的距离
• 端点 $s_1.p_2$ 到 $s_2$ 的距离
• 端点 $s_2.p_1$ 到 $s_1$ 的距离
• 端点 $s_2.p_2$ 到 $s_1$ 的距离
  四者中的最小值。点到线段的距离通过投影判断，若投影在线段上则取垂距，否则取到最近端点的距离。

步骤 $\text{2}$. 构建完全图，边数为 $N(N-1)/2$，使用 $\text{Kruskal}$ 算法求最小生成树，累加边权。

步骤 $\text{3}$. 输出边数（$N-1$）和总长度。

由于 $N\le 100$，多边形顶点数 $P\le 25$，计算所有边对距离的复杂度为 $O(N^2\times P^2)$，约为 $100^2\times 25^2=6.25\times 10^6$，可行。$\text{Kruskal}$ 复杂度 $O(E\log E)$，$E\le 4950$，高效。

代码实现

// Islands
// UVa ID: 889
// Verdict: Accepted
// Submission Date: 2018-12-28
// UVa Run Time: 0.130s
//
// 版权所有（C）2018，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

struct point {
double x, y;
point (double x = 0, double y = 0): x(x), y(y) {}
point operator + (point p) { return point(x + p.x, y + p.y); };
point operator – (point p) { return point(x – p.x, y – p.y); };
point operator * (double k) { return point(x * k, y * k); };
point operator / (double k) { return point(x / k, y / k); };
};

struct segment {
point p1, p2;
segment (point p1 = point(0, 0), point p2 = point(0, 0)): p1(p1), p2(p2) {}
};

typedef segment line;
typedef vector<point> polygon;

double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double cross(point a, point b) { return a.x * b.y – b.x * a.y; }
double norm(point p) { return p.x * p.x + p.y * p.y; };
double abs(point p) { return sqrt(norm(p)); };

double getDistPL(point p, line l)
{
return fabs(cross(l.p2 – l.p1, p – l.p1) / abs(l.p2 – l.p1));
}

double getDistPS(point p, segment s)
{
if (dot(s.p2 – s.p1, p – s.p1) < 0.0) return abs(p – s.p1);
if (dot(s.p1 – s.p2, p – s.p2) < 0.0) return abs(p – s.p2);
return getDistPL(p, s);
}

double getDistSS(segment s1, segment s2)
{
return min(min(getDistPS(s2.p1, s1), getDistPS(s2.p2, s1)),
min(getDistPS(s1.p1, s2), getDistPS(s1.p2, s2)));
}

const int MAXV = 110;

struct edge
{
int u, v;
double w;
edge (int u = 0, int v = 0, double w = 0): u(u), v(v), w(w) {}
bool operator<(const edge &e) const
{
return w < e.w;
}
} edges[10240];

int parent[MAXV], ranks[MAXV], n, m;

void makeSet()
{
for (int i = 0; i < n; i++) parent[i] = i, ranks[i] = 0;
}

int findSet(int x)
{
return (parent[x] == x ? x : parent[x] = findSet(parent[x]));
}

bool unionSet(int x, int y)
{
x = findSet(x), y = findSet(y);
if (x != y) {
if (ranks[x] > ranks[y]) parent[y] = x;
else {
parent[x] = y;
if (ranks[x] == ranks[y]) ranks[y]++;
}
return true;
}
return false;
}

double kruskal()
{
double sum = 0;

makeSet();
sort(edges, edges + m);

for (int i = 0; i < m; i++)
if (unionSet(edges[i].u, edges[i].v))
sum += edges[i].w;
return sum;
}

double getDist(polygon &pg1, polygon &pg2)
{
double d = 1e20;
for (int i = 0; i < pg1.size(); i++)
for (int j = 0; j < pg2.size(); j++)
d = min(d, getDistSS(segment(pg1[i], pg1[(i + 1) % pg1.size()]), segment(pg2[j], pg2[(j + 1) % pg2.size()])));
return d;
}

int main(int argc, char *argv[])
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

int cases;
cin >> cases;
for (int cs = 1; cs <= cases; cs++)
{
cin >> n;
vector<polygon> pgs(n);
for (int i = 0; i < n; i++)
{
int v;
cin >> v;
double x, y;
for (int j = 0; j < v; j++)
{
cin >> x >> y;
pgs[i].push_back(point(x, y));
}
}

m = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
edges[m++] = edge(i, j, getDist(pgs[i], pgs[j]));

cout << "The minimal interconnect consists of " << n – 1;
cout << " bridges with a total length of ";
cout << fixed << setprecision(3) << kruskal() << '\\n';

}

return 0;
}

总结

本题将岛屿连接问题转化为最小生成树问题，关键在于计算两多边形之间的最短距离。通过计算所有边对之间的最短距离并取最小值，得到岛屿间距离。使用 $\text{Kruskal}$ 算法求最小生成树，总长度即为答案。该解法充分利用了几何计算和图论算法，适用于 $N\le 100$ 的规模。该题体现了计算几何与图论的结合。