首页 > 试题广场 >

寻宝

[编程题]寻宝

热度指数：3186 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

亮亮解出了卷轴隐藏的秘密，来到了一片沼泽地。这里有很多空地，而面试直通卡可能埋在任意一块空地中，好在亮亮发现了一堆木材，他可以将木材铺在两个空地之间的沼泽地上。因为亮亮不知道面试直通卡具体在哪一块空地中，所以必须要保证任意一块空地对于亮亮来说是可以抵达的。 “怎么还有鳄鱼！没办法，看来有些空地不能直接到达了。” 亮亮虽然没有洁癖，但是沼泽地实在太臭了，所以亮亮不会循环利用木材。而且木材不能拼接在一起使用，所以亮亮必须要知道在耗费木材最少的情况下，最长的那根木材至少需要多长。

输入描述:

第一行包含两个整数N(1≤N≤10000),M(1≤M≤1000000)。N表示公有N块空地。
接下来M行，每行包含三个整数P(1≤P≤N),Q(1≤Q≤N),K代表P,Q两个间没有鳄鱼，需要耗费K的木材。

输出描述:

一个整数，即耗费木材最少的情况下，最长的那根木材长度。

示例1

输入

输出

算法知识视频讲解

Python

离疏

#问题转化成求图的最小生成树，输出最小生成树里权值最大的边，Kruskal算法
import collections

def find(x):#并查集
    while x!=uni[x]:
        x=uni[x]
    return x

N,M=list(map(int,input().split()))
land=[list(map(int,input().split())) for i in range(M)]
land=sorted(land,key=lambda x:x[2])
uni=list(range(N+1))
count=0
for line in land:
    s,e,v=line#起点，终点，权值
    if s>e:
        s,e=e,s
    s=find(s)
    e=find(e)
    if s==e:
        continue
    else:
        uni[e]=s
        count+=1
    if count==N-1:
        print(v)
        break

发表于 2018-10-01 16:36:32 回复(0)

Python

新鲜菜鸡🐔

暴力版的PRIM算法超时，只能过50%，所以用了简化版的并查集+Kruskal算法

Python代码如下

try:
    def findx(x):
        while x != uni[x]:
            x = uni[x]
        return x
    while 1:
        import collections
        N,M = [int(x) for x in input().split()]
        m_list = []
        for i in range(M):
            temp = [int(x) for x in input().split()]
            m_list.append(temp)
        uni = [i for i in range(N+1)]
        m_list = sorted(m_list,key=lambda x:x[2])
        v_count = 0
        for line in m_list:
            s,e,v = line
            if s>e:
                s,e = e,s
            set_s = findx(s)
            set_e = findx(e)
            if set_e==set_s:
                continue
            else:
                uni[set_e] = set_s
                v_count+=1
            if v_count==N-1:
                print(v)
                break
except EOFError:
    pass

发表于 2018-07-04 14:10:01 回复(0)