题解 | 古代符文路径的激活

from re import L
import sys

# 比较原则一看就是贪心

def get_data():
    stones = [] # n个
    inner_links_list = [] # n组
    outer_links_list = [] # n-1组（从0到1，从1到2...
    lines = [line[:-1] for line in sys.stdin]
    n = int(lines[0])
    for i in range(n):
        data = lines[i*3+1].split()
        data = [int(d) for d in data]
        stones.append(data)

        if lines[i*3+2] != "0":
            data = lines[i*3+2].split(" ")
            data = [[int(k) for k in d.split("-")] for d in data]
            inner_links_list.append(data)
        else:
            inner_links_list.append([])
        
        if i < n-1:
            if lines[i*3+3] != "0":
                data = lines[i*3+3].split(" ")
                data = [[int(k) for k in d.split("-")] for d in data]
                outer_links_list.append(data)
            else:
                outer_links_list.append([])

    
    return stones, inner_links_list, outer_links_list

def solve(stones, inner_links_list, outer_links_list):
    n = len(stones)

    # n-1组
    outer_links_dict_lists = [
        {a:b for a,b in outer_links}
        for outer_links in outer_links_list
    ]

    # 我将未占用理解为，没有被内部灵脉占用，被外部能量桥占用肯定无所谓
    # 但是，这里为了方便，会先过滤掉那些已经被后续的外部能量桥占用的marks，
    # 以及必须被先序的能量桥所使用

    # 潜在的内部link 
    # n组
    potential_links_list = []

    for i in range(n):
        used_marks = set()
        for a,b in inner_links_list[i]:
            used_marks.add(a)
            used_marks.add(b)

        starts = []
        ends = []

        # 第一组的起点是任意的
        if i == 0:
            for a in stones[i]:
                starts.append(a)

        # 中间组的link起点必须是前序能量桥的终点
        else:
            for a, b in outer_links_list[i-1]:
                starts.append(b)

        # 最后一组的终点是任意的
        if i == n - 1:
            for a in stones[i]:
                ends.append(a)

        # 中间组的link起点必须是后序能量桥的起点
        else:
            for a, b in outer_links_list[i]:
                ends.append(a)

        new_links = []
        for a in starts:
            if a not in used_marks:
                for b in ends:
                    if b not in used_marks:
                        if a != b:
                            new_links.append((a,b))

        old_links = []
        for a,b in inner_links_list[i]:
            if a in starts and b in ends:
                old_links.append((a,b))
            if b in starts and a in ends:
                old_links.append((b,a))

        # 次要排序
        # 输入铭文编号更小
        old_links.sort(key=lambda x: x[0])
        new_links.sort(key=lambda x: x[0])
        # 主要排序
        # 两者之和更小
        old_links.sort(key=lambda x: x[0]+x[1])
        new_links.sort(key=lambda x: x[0]+x[1])

        old_links.extend(new_links)
        potential_links_list.append(old_links)


    # 当前选择到第i块灵石, 入口符文是a
    path = []
    def dfs(i, a):
        path.append(a)

        data = potential_links_list[i]
        data = [link for link in data if link[0] == a]

        if i == n-1:
            path.append(data[0][1])
            return True

        # 然后尝试连接，如果无法连接，那么整个方案就是需要回退
        for a,b in data:
            path.append(b)
            # 根据b查询outer link
            nb = outer_links_dict_lists[i][b]
            if dfs(i+1, nb):
                return True
            path.pop() 

        path.pop()
        return False
    
    for a,b in potential_links_list[0]:
        if dfs(0, a):
            print(*path)
            return
        
    print(-1)

stones, inner_links_list, outer_links_list = get_data()
solve(stones, inner_links_list, outer_links_list)

题目的计算量不大，对算法性能其实要求不严格，一个不过分暴力的dfs就可以解决。

1. 外部能量桥（符文石头之间的link）是单向的，不可新增，而且数量有限，他们极大限制了各个符文石头内部的有效符文link（灵脉）的数量。
2. 内部符文link比较容易忽略的一点是，他们的方向是双向的。4-16意味着4-16和16-4
3. 可以提前算出所有石头的有效内部符文link（包括可能可以新建的，其数量最多不会超过M^2/2，总体总数不会超过M^2/2*N），并事先按照题目要求的三大优先级进行排序
4. 使用dfs遍历所有可能，直到找到第一个解，该解必定最优（因为顺序已经事先排列好）