题解

问题分析

题目要求最大化“未回答题目中的最低价值”，核心逻辑可转化为：通过二分答案确定一个阈值，判断能否用有限路径覆盖所有低于该阈值的题目，从而找到最大可行阈值。

关键思路

1. 二分答案：假设目标阈值为 ( x )，需判断所有价值小于 ( x ) 的题目（必须被回答）能否被 ( n+1 ) 条路径覆盖。
2. 路径覆盖模型：题目间的“后续关系”构成有向图，覆盖所有目标题目（价值 < ( x )）的问题等价于求该有向图的最小路径覆盖数。
3. DAG 最小路径覆盖：通过强连通分量（SCC）缩点将有向图转化为 DAG，再利用二分图最大匹配求解（最小路径数 = 缩点后节点数 - 最大匹配数）。

具体步骤

1. 二分答案范围：阈值 ( x ) 的可能范围为 ( [0, \text{max_v} + 1] )（(\text{max_v}) 是所有题目价值的最大值）。
2. 构建目标子图：对每个候选 ( x )，筛选出所有价值 < ( x ) 的题目，构建仅包含这些题目的子图（保留原后续关系）。
3. 缩点处理：用 Tarjan 算法找到子图的所有 SCC，将每个 SCC 缩为一个节点，形成 DAG。
4. 二分图匹配：将缩点后的 DAG 转化为二分图（拆点法），用 Hopcroft-Karp 算法求最大匹配，计算最小路径覆盖数。
5. 可行性判断：若最小路径数 ≤ ( n+1 )，则 ( x ) 可行，尝试更大值；否则尝试更小值。

代码实现

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    for _ in range(t):
        n = int(input[ptr])
        m = int(input[ptr+1])
        ptr +=2
        v = [0]*(m+1)  # 1-based
        a = [[] for _ in range(m+1)]  # a[u]是后续题目列表
        max_v = 0
        for u in range(1, m+1):
            vi = int(input[ptr])
            ki = int(input[ptr+1])
            ptr +=2
            ai = list(map(int, input[ptr:ptr+ki]))
            ptr += ki
            v[u] = vi
            a[u] = ai
            if vi > max_v:
                max_v = vi
        k = n + 1  # 可用路径数
        
        # 二分答案：找最大x使得check(x)为True
        low = 0
        high = max_v + 1
        best = 0
        
        def check(x):
            # 收集所有v_i < x的节点
            S = []
            for u in range(1, m+1):
                if v[u] < x:
                    S.append(u)
            s = len(S)
            if s == 0:
                return True
            # 映射节点到0..s-1
            node_id = {u: idx for idx, u in enumerate(S)}
            # 构建子图边
            edges = [[] for _ in range(s)]
            for u in S:
                u_idx = node_id[u]
                for v_node in a[u]:
                    if v_node in node_id:
                        v_idx = node_id[v_node]
                        edges[u_idx].append(v_idx)
            # Tarjan算法求SCC
            index = 0
            indices = [-1]*s
            low = [0]*s
            on_stack = [False]*s
            stack = []
            scc_list = []
            
            def strongconnect(v):
                nonlocal index
                indices[v] = index
                low[v] = index
                index +=1
                stack.append(v)
                on_stack[v] = True
                for w in edges[v]:
                    if indices[w] == -1:
                        strongconnect(w)
                        low[v] = min(low[v], low[w])
                    elif on_stack[w]:
                        low[v] = min(low[v], indices[w])
                if low[v] == indices[v]:
                    scc = []
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        scc.append(w)
                        if w == v:
                            break
                    scc_list.append(scc)
            
            for v_node in range(s):
                if indices[v_node] == -1:
                    strongconnect(v_node)
            c = len(scc_list)
            # 分配scc_id
            scc_id = [0]*s
            for i in range(c):
                for node in scc_list[i]:
                    scc_id[node] = i
            # 构建DAG边（去重）
            dag_edges = set()
            for u in range(s):
                for v_node in edges[u]:
                    if scc_id[u] != scc_id[v_node]:
                        dag_edges.add( (scc_id[u], scc_id[v_node]) )
            # 拆点二分图：左节点u_out(0..c-1)，右节点v_in(0..c-1)
            adj = [[] for _ in range(c)]
            for u, v_node in dag_edges:
                adj[u].append(v_node)
            # Hopcroft-Karp算法求最大匹配
            pair_u = [-1]*c
            pair_v = [-1]*c
            dist = [0]*c
            
            def bfs():
                queue = deque()
                for u in range(c):
                    if pair_u[u] == -1:
                        dist[u] = 0
                        queue.append(u)
                    else:
                        dist[u] = float('inf')
                dist_null = float('inf')
                while queue:
                    u = queue.popleft()
                    if dist[u] < dist_null:
                        for v_node in adj[u]:
                            if pair_v[v_node] == -1:
                                dist_null = dist[u] + 1
                            elif dist[pair_v[v_node]] == float('inf'):
                                dist[pair_v[v_node]] = dist[u] + 1
                                queue.append(pair_v[v_node])
                return dist_null != float('inf')
            
            def dfs(u):
                for v_node in adj[u]:
                    if pair_v[v_node] == -1 or (dist[pair_v[v_node]] == dist[u] + 1 and dfs(pair_v[v_node])):
                        pair_u[u] = v_node
                        pair_v[v_node] = u
                        return True
                dist[u] = float('inf')
                return False
            
            result = 0
            while bfs():
                for u in range(c):
                    if pair_u[u] == -1:
                        if dfs(u):
                            result +=1
            min_paths = c - result
            return min_paths <= k
        
        # 二分查找
        while low <= high:
            mid = (low + high) // 2
            if check(mid):
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        if best > max_v:
            print("AK")
        else:
            print(best)

if __name__ == "__main__":
    main()

复杂度分析

• 二分答案：( O(\log \text{max_v}) )（约 30 次）。
• 每次检查：
  • 构建子图：( O(m + \text{total_k}) )（(\text{total_k}) 为后续题目总数，≤ ( 500 \times 500 = 250000 )）。
  • Tarjan 算法：( O(s + e) )（( s ) 为目标节点数，( e ) 为子图边数）。
  • Hopcroft-Karp 算法：( O(\sqrt{c} \cdot e_{\text{dag}}) )（( c ) 为缩点后节点数，( e_{\text{dag}} ) 为 DAG 边数）。

整体复杂度可接受，适用于题目数据范围。