拼多多-Anniversary

2019-07-27  本文已影响0人  葡萄肉多

拼多多王国的城市和道路的拓扑结构比较特别,是一个树状结构:

  1. 每个城市是树的一个节点;
  2. 城市之间的道路是树的一条边;
  3. 树的根节点是首都。

拼多多周年庆马上就要到了,这是拼多多王国的一个大日子。为了活跃气氛,国王想在道路上布置花灯。花灯可是很贵的东西,尽管国王想要在所有道路上都布置花灯,但是如果要花太多钱的话,是过不了财政大臣那一关的。国王把这个计划告诉财政大臣,最后他们商讨出来这么一个方案:

  1. 一条道路要么不布置花灯,要么整条布置花灯,不能选择其中的某一段布置;
  2. 除非没有道路通向首都,否则至少为一条通向首都的道路布置花灯;
  3. 所有布置花灯的道路构成的子图是连通的,这保证国王从首都出发,能通过只走布置了花灯的道路,把所有的花灯游览完;
  4. 如果某个城市(包括首都)有大于等于2条道路通向子城市,为了防止铺张浪费,最多只能选择其中的两条路布置花灯;
  5. 布置花灯的道路的总长度设定一个上限。
    在上述方案下,国王想要使得布置花灯的道路长度越长越好,你帮国王想想办法。

输入描述
每个测试输入包含1个测试用例。
输入的第一行是一个正整数m,0<m<=9900,表示布置花灯的道路的总长度的上限。
输入的第二行是一个正整数n,n<=100,表示城市的个数。
紧接着是n-1行输入,每行三个正整数u、v、d,表示下标为u的城市有一条长度为d的道路通向它的一个子城市v,其中0<=u<n,0<=v<n,0<d<=100。


输出描述
输出一个正整数,表示能布置花灯的道路长度的最大值

输入例子1:

5
5
0 1 1
0 2 2
0 3 3
0 4 4

输出例子1:

5

思路

dfs搜索所有可能路径的长度值。包括一个节点所有的儿子中选1个儿子,选2个儿子的情况(最多只能选择两条路布置)。
步骤如下:

  1. 根据输入,得到所有节点的父节点字典和两两节点连通关系字典;
  2. 找到根节点;
  3. children集合维护每个节点的所有孩子节点,sets记录每个子节点的候选路径列表,对于候选路径集合,枚举三种情况:
  1. 找出根节点候选集合中不超过上限值的最大值,即为答案。

代码

from collections import defaultdict


limit = int(input())
city = int(input())
tree = defaultdict(lambda :dict())
parent = {}
visited = {}
root = None

# build tree
for _ in range(city - 1):
    s = input().split()
    u, v, d = int(s[0]), int(s[1]), int(s[2])
    if d > limit:
        continue
    if not root:
        root = u
    parent[v] = u
    tree[u][v] = d

# find root
while parent.get(root, -1) != -1:
    root = parent.get(root)
    
'''
cand:候选队列,存放当前节点的所有可能路径长度
children:存放以当前节点为根节点的所有的子节点
sets:存放以当前节点为根节点的子树下,每个孩子节点的候选队列
'''
def dfs(u):
    if u not in visited:
        cand = set()
        cand.add(0)
        if u in tree:
            sets = []
            children = []
            for v in tree[u]:
                children.append(v)
                sets.append(dfs(v))
            for i in range(len(sets)):
                d = tree[u][children[i]]
                for c in sets[i]:
                    if d + c <= limit:
                        cand.add(d + c)
                for j in range(i + 1, len(sets)):
                    d2 = tree[u][children[j]]
                    for c in sets[i]:
                        for c2 in sets[j]:
                            if c + c2 + d + d2 <= limit:
                                cand.add(c + c2 + d + d2)
        visited[u] = cand
    return visited[u]


print(max(dfs(root)))
上一篇 下一篇

猜你喜欢

热点阅读