結果

問題 No.679 不思議マーケット
ユーザー gew1fw
提出日時 2025-06-12 19:56:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 3,585 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 72,960 KB
最終ジャッジ日時 2025-06-12 19:57:26
合計ジャッジ時間 2,001 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    conditions = {}
    for _ in range(m):
        parts = sys.stdin.readline().split()
        g_i = int(parts[0])
        r_i = int(parts[1])
        h_list = list(map(int, sys.stdin.readline().split()))
        conditions[g_i] = h_list

    # 构建DAG
    in_degree = {i: 0 for i in range(1, n+1)}
    adj = {i: [] for i in range(1, n+1)}

    # 添加条件依赖
    for g_i, h_list in conditions.items():
        for h_j in h_list:
            adj[h_j].append(g_i)
            in_degree[g_i] += 1

    # 拓扑排序
    queue = deque()
    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append(i)
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 处理没有条件的商品
    for i in range(1, n+1):
        if i not in conditions:
            # 这些商品必须被放在任何位置，但为了最大化条件满足，我们将其安排在可能影响条件的位置
            # 这里直接将它们添加到拓扑排序的最前面，以确保它们的条件被满足
            # 但这样可能不正确，因为它们的条件可能依赖于其他商品
            # 因此，可能需要重新处理
            pass

    # 重新构建拓扑排序，包括那些没有条件的商品
    # 这个部分可能需要更复杂的处理，例如将所有没有条件的商品视为必须被处理的节点，并安排在它们的条件依赖它们的g_i之前
    # 这可能需要重新构建DAG，包括所有商品

    # 重新构建DAG，包括所有商品的条件
    in_degree = {i: 0 for i in range(1, n+1)}
    adj = {i: [] for i in range(1, n+1)}

    for g_i, h_list in conditions.items():
        for h_j in h_list:
            adj[h_j].append(g_i)
            in_degree[g_i] += 1

    # 拓扑排序
    queue = deque()
    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append(i)
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 处理没有条件的商品
    for i in range(1, n+1):
        if i not in conditions:
            # 这些商品必须被放入购物车，无论它们的位置如何
            # 所以，我们需要确保它们在任何情况下都被处理
            # 这可能意味着，它们可以被放置在任何位置，但为了满足其他商品的条件，可能需要将它们放置在前面
            # 这里，我们将它们添加到拓扑排序的最前面
            if i not in topo_order:
                topo_order.insert(0, i)

    # 现在，模拟购物车的放入过程
    cart = set()
    count = 0
    for item in topo_order:
        if item in conditions:
            h_list = conditions[item]
            # 检查所有h_list中的商品是否都在cart中
            satisfied = True
            for h in h_list:
                if h not in cart:
                    satisfied = False
                    break
            if satisfied:
                cart.add(item)
                count += 1
        else:
            # 没有条件，必须放入
            cart.add(item)
            count += 1

    print(count)

if __name__ == '__main__':
    main()
0