2011-08-09 08:32:39Morris
a207. 精準覆蓋問題(Exact cover)
a207. 精準覆蓋問題(Exact cover)
內容 ：
給定一個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".
範例輸入 ：
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
範例輸出 ：
3 3
提示
：
× 測資難度偏易, 希望大家能夠通過
× 極難測資已經拔除, 瘋狂剪枝 DFS 可通過
出處
：
/**********************************************************************************/
/* Problem: a207 "精準覆蓋問題(Exact cover)" from exact cover problem | DFS | Dancing Links*/
/* Language: C */
/* Result: AC (224ms, 620KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-06 22:52:32 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Maxv 100000
struct DacingLinks {
int left, right;
int up, down;
int data, ch, rh;
}DL[100001 + 1001];
int s[1001], o[1001], head, len, size;
void Remove(int c) {
DL[DL[c].right].left = DL[c].left;
DL[DL[c].left].right = DL[c].right;
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].right; j != i; j = DL[j].right) {
DL[DL[j].down].up = DL[j].up;
DL[DL[j].up].down = DL[j].down;
s[DL[j].ch]--;
}
}
}
void Resume(int c) {
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].left; j != i; j = DL[j].left) {
DL[DL[j].down].up = j;
DL[DL[j].up].down = j;
s[DL[j].ch]++;
}
}
DL[DL[c].right].left = c;
DL[DL[c].left].right = c;
}
void DFS(int k) {
if(k > len) return;
if(DL[head].right == head) {
if(k < len) len = k;
return;
}
int t = Maxv, c, i, j;
for(i = DL[head].right; i != head; i = DL[i].right) {
if(s[i] < t) {
t = s[i], c = i;
}
}
Remove(c);
for(i = DL[c].down; i != c; i = DL[i].down) {
o[k] = i;
for(j = DL[i].right; j != i; j = DL[j].right)
Remove(DL[j].ch);
DFS(k+1);
for(j = DL[i].left; j != i; j = DL[j].left)
Resume(DL[j].ch);
}
Resume(c);
}
int new_node(int up, int down, int left, int right) {
DL[size].up = up, DL[size].down = down;
DL[size].left = left, DL[size].right = right;
DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
return size++;
}
void init(int m) {
size = 0;
head = new_node(0, 0, 0, 0);
int i;
for(i = 1; i <= m; i++) {
new_node(i, i, DL[head].left, head);
DL[i].ch = i, s[i] = 0;
}
}
main() {
int n, m, a, b, x, r, k, C = 0;
while(scanf("%d %d", &n, &m) != EOF) {
init(m);
for(a = 1; a <= n; a++) {
scanf("%d", &x);
int row = -1;
while(x--) {
scanf("%d", &r);
DL[size].ch = r, s[r]++;
if(row == -1) {
row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
DL[row].rh = a;
}else {
k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
DL[k].rh = a;
}
}
}
len = Maxv, DFS(0);
if(len != Maxv) printf("%d\n", len);
else puts("No");
}
return 0;
}
上一篇：a206. 學長的鬼腳圖 (二)
下一篇：d705. 判断质数（二）