回『原創/不分類題庫』
a207. 精準覆蓋問題(Exact cover)
標籤 : DFS Dancing Links exact cover problem
通過比率 : 42人/60人 ( 70% ) [非即時]
評分方式：
Tolerant

最近更新 : 2011-08-27 21:01

內容

給定一個01矩陣, 現在選擇一些行, 使得每一列有且只有一個 1,
例子如下 :

這裡是 6 行 7 列 的矩陣, 我們取行集合{1, 4, 5}, 便可使每一列有且僅有一個 1

輸入說明

有多組測資,

每組第一行有兩個整數 n, m, 代表有 n 行, m 列 (1 ≦ n, m ≦ 1000)

接下來有 n 行,

每行的第一個數字 C (1 ≦ C  ≦ 100), 代表有幾個 1 在該行,

接下來有 C 個整數, 代表該列的元素值為 1, 且已排序好

輸出說明
輸出取的最少個數, 如果為 0, 請輸出 "No".
範例輸入 #1 
6 7
3 3 5 6
3 1 4 7
3 2 3 6
2 1 4
2 2 7
3 4 5 7

6 7
3 1 4 7
2 1 4
3 4 5 7
3 3 5 6
4 2 3 6 7
2 2 7
範例輸出 #1 
3
3
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (100%): 30.0s , <1M
提示 ：

×　測資難度偏易, 希望大家能夠通過

×　極難測資已經拔除, 瘋狂剪枝 DFS 可通過

標籤:
DFS Dancing Links exact cover problem
出處:
[管理者： morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」