牛牛生活在网格世界中,在网格世界中人们出行只能通过网格上的边来进行。现在牛牛管理着 n 个城市,每个城市在网格世界中都以一个矩形来表示,牛牛想在这 n 个城市之间铺上水泥路方便人们出行,网格上一条边铺上水泥所需要的花费为 1 。但是为了节约预算,牛牛给你这 n 个城市的左下坐标(x0,y0)和右上坐标(x1,y1),牛牛想让你告诉他让这 n 个城市联通所需要的最小花费是多少呢。(如图花费为6)
第一行为一个 n,表示城市数量。接下来有 n 行,每行有四个整数x0,y0,x1,y1,表示城市坐标。
输出为一行,表示答案。
3 0 0 1 1 2 2 3 3 4 4 5 5
4
使用的最小生成树的Kruskal算法,计算的距离公式需要注意一下.
以x轴为例:给定两个城市4个x(x1,x2,x3,x4), 假设没有重叠(右侧城市的最左横坐标大于左侧城市的最右横坐标). 最小距离就是右侧城市的最小x去减左侧城市的最大x,我们知道x1<x2,x3<x4,但是我们不知道x1和x3谁大谁小,
如果x1>x3,就是x1-x4;
如果x1<x3,就是x3-x2;
综合就是max(x1,x3)-min(x2,x4).
dist = max(0,max(x1,x3)-min(x2,x4))+max(0,max(y1,y3)-min(y2,y4))
class UnionFind: #并查集 def __init__(self,n): self.father = list(range(n)) def find(self,i): if i == self.father[i]: return i else: self.father[i] = self.find(self.father[i]) return self.father[i] def merge(self,i,j,i_father,j_father): #使成为一棵树 if i_father<j_father: self.father[j_father]=i_father else: self.father[i_father]=j_father n = eval(input()) xy_list=[] for i in range(n): xy_list.append(tuple(map(eval,input().split()))) Dist = [] for i in range(n-1): x1,y1,x2,y2=xy_list[i] for j in range(i+1,n): x3,y3,x4,y4=xy_list[j] d = max(0,max(x1,x3)-min(x2,x4))+max(0,max(y1,y3)-min(y2,y4)) Dist.append((d,i,j)) Dist.sort() ans = 0 cnt = 0 uf = UnionFind(n) for d,i,j in Dist: i_father,j_father =uf.find(i),uf.find(j) if i_father==j_father: continue else: uf.merge(i,j,i_father,j_father) ans+=d cnt+=1 if cnt == n-1: break print(ans)