P4929 【模板】舞蹈链(DLX)

    • 135通过
    • 393提交
  • 题目提供者 Ebola
  • 评测方式 云端评测
  • 标签 剪枝 搜索 状态压缩,状压 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    本题是舞蹈链模板——精确覆盖问题

    题目描述

    给定一个$N$行$M$列的矩阵,矩阵中每个元素要么是1,要么是0

    你需要在矩阵中挑选出若干行,使得对于矩阵的每一列$j$,在你挑选的这些行中,有且仅有一行的第$j$个元素为$1$

    输入输出格式

    输入格式:

    第一行两个数$N,M$

    接下来$N$行,每行$M$个数字0或1,表示这个矩阵

    输出格式:

    一行输出若干个数表示答案,两个数之间用空格隔开,输出任一可行方案均可,顺序随意

    若无解,输出“No Solution!”(不包含引号)

    输入输出样例

    输入样例#1: 复制
    3 3
    0 0 1
    1 0 0
    0 1 0
    输出样例#1: 复制
    2 1 3
    输入样例#2: 复制
    3 3
    1 0 1
    1 1 0
    0 1 1
    输出样例#2: 复制
    No Solution!

    说明

    $N,M\leq 500$

    保证矩阵中1的数量不超过$5000$个

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。