首页 > 试题广场 >

牛牛铺路

[编程题]牛牛铺路

热度指数：107 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛生活在网格世界中，在网格世界中人们出行只能通过网格上的边来进行。现在牛牛管理着 n 个城市，每个城市在网格世界中都以一个矩形来表示，牛牛想在这 n 个城市之间铺上水泥路方便人们出行，网格上一条边铺上水泥所需要的花费为 1 。但是为了节约预算，牛牛给你这 n 个城市的左下坐标(x₀,y₀)和右上坐标(x₁,y₁)，牛牛想让你告诉他让这 n 个城市联通所需要的最小花费是多少呢。(如图花费为6)

输入描述:

第一行为一个 n，表示城市数量。
接下来有 n 行，每行有四个整数x₀,y₀,x₁,y₁，表示城市坐标。

输出描述:

输出为一行，表示答案。

示例1

输入

输出

算法知识视频讲解

我是赵同学

使用的最小生成树的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).

但是还有一种情况就是重叠,(右侧城市的最左横坐标小于或等于左侧城市的最右横坐标) . 这时,右侧城市的最小x去减左侧城市的最大x就是一个负数,但是实际上这两种城市在x轴上已经重叠,也就是说它们的距离是0.

y轴是相同的.

所以综上给出;距离公式:

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)

编辑于 2022-04-03 11:26:26 回复(0)