4333. 高速公路
某国家有 N 个城市,编号 1∼N。
其中第 i 个城市的位置坐标为 (xi,yi)。
该国家的高速公路系统十分差劲,到目前为止只有 M 对城市之间存在高速公路直接连接。
因此,政府决定新修一些高速公路,从而使得任意两个城市之间都能通过高速公路互相抵达。
已知高速公路都是双向的,且任意两个城市之间要修建或已修建的高速公路的长度都等于两城市之间的直线距离。
为了节约成本,政府希望新修的高速公路的长度之和尽可能小。
请你提供一种合适的修建方案。
注意,每个高速公路必须在一端城市进入,然后在另一端城市离开,不存在中途离开或变道的可能。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含两个整数 xi,yi。
再一行包含整数 M。
最后 M 行,每行包含两个整数 a,b,表示城市 a 和 b之间存在一条高速公路。每对城市之间最多存在一条高速公路。
输出格式
若干行,每行包含两个整数,表示一条新修道路的两端城市编号。
如果无需新修任何高速公路,则输出空文件即可。
如果方案不唯一,输出任意合理方案均可。
数据范围
1≤N≤750,
0≤M≤1000,
−10000≤xi,yi≤10000,
1≤a,b≤N。
输入样例:
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2
输出样例:
1 6
3 7
4 9
5 7
8 3
写法
学校里这道题留做作业。作为小白,这里用的kruskal算法,但是真的不太熟练,纯纯小白(板子背熟了不会用hh),这里只提供我的Java写法,只为了将来有人需要的时候仅作参考。
import java.io.*;
import java.util.*;
import java.lang.*;
/**
* Highways POJ - 1751 使用Kruskal来解决这道题,要求根据已给条件,继续修路,建立一个最小生成树
*/
public class Main {
//数据的规模,N个点M条边 实际录入n,m
static int N = 100010, M = 500010, n, m;
//使用并查集的方式,需要格外维护一个数组
static int[] p = new int[M];
//用Edge自定义的来存储边
static Edge[] edge = new Edge[M];
//定义两个数组,用来存储题目中所给的所有坐标信息
static int[] x = new int[N], y = new int[N];
static int Int(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] arrStr = br.readLine().split(" ");
//表明N个城市
n = Int(arrStr[0]);
//初始化一下存储边的数组,防止空指针异常
Arrays.fill(edge,new Edge(0,0,0));
//维护并查集,每一个数代表一个各自的结点
for (int i = 1; i <= n; i++) p[i] = i;
//一共循环n次,开始录入坐标数据
for (int i = 1; i <= n; i++) {
arrStr = br.readLine().split(" ");
x[i] = Int(arrStr[0]);
y[i] = Int(arrStr[1]);
}
//定义一个变量,用来临时存储有多少条边
int t = 1;
//定义两个指针,前后,第一次表示 第一个城市的距离 和 第二个城市的距离
//使用前面的坐标数组,算出来他们之间的距离,然后存储到边的数组中
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
edge[t] = new Edge(i, j, Math.sqrt(Math.pow(x[j] - x[i], 2) + Math.pow(y[j] - y[i], 2)));
t++;
}
}
//剩下的m次表示ab两城市已经连接,那么使用并查集将其合并成一个集合
m = Int(br.readLine());
while (m-- > 0) {
arrStr = br.readLine().split(" ");
int a = Int(arrStr[0]);
int b = Int(arrStr[1]);
p[find(a)] = find(b);
}
//开始我们的Kruskal算法,对于存储的所有边进行升序排序
Arrays.sort(edge, 1, t + 1);
//遍历t次,因为一共需要t条边
for (int i = 1; i <= t; i++) {
//每次取出边的领点,起点和终点
int s = edge[i].s;
int tt = edge[i].t;
double c = edge[i].w;
//判断两个点在不在一个集合,如果不再,那么表明此时可以加入到一个集合中
if (find(s) != find(tt)) {
p[find(s)] = find(tt);
//找到了加入,并且输出当前这一组,表示需要建路
bw.write(s + " " + tt + "\n");
}
}
bw.flush();
br.close();
bw.close();
}
/**
* 并查集,使用压缩路径的方式,查找当前u在某个集合中
* @param u
* @return
*/
static int find(int u) {
if (p[u] != u) p[u] = find(p[u]);
return p[u];
}
}
/**
* 自定义的边,实现Comparable接口用来实现比较规则,使用compareTo进行升序排序
*/
class Edge implements Comparable<Edge> {
int s;
int t;
double w;
public Edge(int s, int t, double w) {
this.s = s;
this.t = t;
this.w = w;
}
@Override
public int compareTo(Edge e) {
return Double.compare(this.w, e.w);
}
}