UVALive 4872 Underground Cables 最小生成树
题目链接:
题目
Underground Cables
Time Limit: 3000MS
Memory Limit: Unknown
64bit IO Format: %lld & %llu
问题描述
A city wants to get rid of their unsightly power poles by moving their power cables underground. They have a list of points that all need to be connected, but they have some limitations. Their tunneling equipment can only move in straight lines between points. They only have room for one underground cable at any location except at the given points, so no two cables can cross.
Given a list of points, what is the least amount of cable necessary to make sure that every pair of points is connected, either directly, or indirectly through other points?
输入
There will be several test cases in the input. Each test case will begin with an integer N(2$ \le$N$ \le$1, 000), which is the number of points in the city. On each of the next N lines will be two integers, X and Y(- 1, 000$ \le$X, Y$ \le$1, 000), which are the (X, Y) locations of the N points. Within a test case, all points will be distinct. The input will end with a line with a single 0.
输出
For each test case, output a single real number, representing the least amount of cable the city will need to connect all of its points. Print this number with exactly two decimal places, rounded. Print each number on its own line with no spaces. Do not print any blank lines between answers.
样例
input
4
0 0
0 10
10 0
10 10
2
0 0
10 10
0
output
30.00
14.14
题意
给你n个点,求最少的线缆使得所有的点连在一起
题解
假设存在两根线交叉,那么明显存在一个不交叉的方案使这四个点连通,并且线缆总长度还要更小,所有我们构建完全图跑一遍最短生成树,是可以保证不会出现交叉边的。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int n;
struct Point {
int x, y;
}pt[maxn];
struct Edge {
int u, v;
double w;
Edge(int u, int v, double w) :u(u), v(v), w(w) {}
Edge() {}
bool operator < (const Edge& e) {
return w < e.w;
}
}egs[maxn*maxn];
double dis(const Point &p1, const Point &p2) {
return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + 1.0*(p1.y - p2.y)*(p1.y - p2.y));
}
int fa[maxn];
int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); }
void init() {
for (int i = 0; i <= n; i++) fa[i] = i;
}
int main() {
while (scanf("%d", &n) == 1 && n) {
init();
int tot = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d", &pt[i].x, &pt[i].y);
for (int j = 0; j < i; j++) {
egs[tot++] = Edge(j, i, dis(pt[j], pt[i]));
}
}
sort(egs, egs + tot);
double ans = 0;
for (int i = 0; i < tot; i++) {
Edge& e = egs[i];
int pu = find(e.u);
int pv = find(e.v);
if (pu != pv) {
ans += e.w;
fa[pv] = pu;
}
}
printf("%.2lf\n", ans);
}
return 0;
}
最新文章
- python使用总结
- FAQ_1_陌生的VERSION.SDK_INT
- 14.Apache配置
- GridView官方教程及示例
- Oracle数据文件管理
- [Everyday Mathematics]20150131
- C#泛型对类型参数的推断
- POJ 1696 Space Ant 卷包裹法
- MFC消息映射与命令传递
- MVC下form表单一次上传多种类型的图片(每种类型的图片可以上传多张)
- xinetd被动服务唤醒
- 强化学习(七)时序差分离线控制算法Q-Learning
- 【SparkStreaming学习之一】 SparkStreaming初识
- Arch Linux 软件包的查询及清理
- SpringCloud系列五:Ribbon 负载均衡(Ribbon 基本使用、Ribbon 负载均衡、自定义 Ribbon 配置、禁用 Eureka 实现 Ribbon 调用)
- C# Excel导入数据
- Linux 防火墙:Netfilter iptables
- Anaconda部署python环境
- 对linux安装中文字体库
- Json Web Token JJWT