批改娘 10038. Fast Covering Problem

1. 題目背景
2. 題目描述
3. 輸入格式
4. 輸出格式
5. 範例輸入
6. 範例輸出
7. 提示
8. Solution

題目背景

終於把所有練習題都放上 Judge Girl，測資都已經確認過一遍，某 M 打算離開一陣子。「反正是個令人唾棄的助教吧 …」

題目描述

考試出題總很難讓所有人滿意，老師決定給予學生們選擇考試出題方向，但每一個人只能提出兩種意見，接著老師會出一套方案滿足每一位學生的其中一種意見。由於出一套題步驟繁瑣，把數個意見出在同一題非常困難，最後每一種意見將單獨被出成一道題。

由於助教們要負責出測資、檢驗測資正確與可行性，希望題目數量越少越好，否則助教會忙翻天。現在要找到最少題目來滿足所有學生的需求。

例如 :

現在有 4 名學生的意見
四名學生分別提案 $(0, 1), (100, 1), (100, 0), (100, 200)$
如果選擇 ${ 0, 100 }$ 或者是 ${ 1, 100 }$ 都是最好的選擇，助教只需要完成 2 題的檢驗。相反地，如果 ${0, 100, 200 }$ 雖然可以滿足所有學生，但需要出成 3 道題目。

輸入格式

只有一組測資，每組第一行會有一個整數 $N$，表示有多少位學生，接下來會有 $N$ 行，每 $i$ 行上會有兩個整數 $A_i, B_i$ 表示第 $i$ 個學生的出題意見。

$0 < N \le 1000$
$0 \le A_i, \; B_i \le 10000$
意見類型總數不超過 100 種

輸出格式

對於每一組測資輸出一行，表示最少要準備的方案數量能滿足所有學生。

範例輸入

範例輸出

提示

DLX

Solution

當年在 NCPC 搞不出來的 Problem I Christmas Gifts (NP-hard)，在賽後用 DLX 運行效果不錯，在啟發函數加上延遲標記更是屹立排名前數位已久。最近又因為平行把題目挖回來討論，在去年釣到大一學弟來解，便以飛快的速度擊破測資，最後達到加速 20x。再把當初需要跑 30 秒的測資來運行，現在只需要短短的 50ms。

原本要拿來出平行題目，看到這麼驚人的速度，想必就不要出題。

通用解法 DLX 加上啟發式函數就能解決最少重複覆蓋，然而在圖論的最少點集覆蓋問題中，性質又變得更加強烈。當不選某一個點時，必然與其相連的邊為了要覆蓋，另一端必然成為必選點。這時候搜索空間大幅度地下降。若在一般 DLX 算法中提及的最少可能的列中，窮舉某行來覆蓋一些列，那麼就很難看到搜索空間下降的性質。

因此，步驟簡單分成下列步驟：

將圖轉換成某行可以覆蓋哪幾列，轉換成 Dancing Links 的格式
找到可以覆蓋最多尚未覆蓋列最多的那一行
1. 選擇這一行，並且移除這一行所有覆蓋列，遞迴窮舉。
2. 移除這一行，選擇必選行，並嘗試移除等價行。

附錄：和交通大學謝旻錚(Min-Zheng Shieh) 教練的討論

在想確實能用 dancing links 來搞，還要搭配維護 degree order，不過這算法吳邦一老師是說 worst case 為 3 regular graph。
另外先前找過日本人 iwi 的論文，他也搞了個高級 VC solver 並做了測試，詳見論文 Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover, Takuya Akiba, Yoichi Iwata

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#define MAXNODE 100000
#define MAXCOL 5005
#define MAXN 5005
struct DancingNode {
    int left, right, up, down;
    int ch, rh;
} DL[MAXNODE];
struct HelperNode {
    int head, size, next, prev;
} HN[MAXNODE];
int help_head;
int s[MAXCOL];
int head, size, Ans, Dep;
int markStk[MAXNODE], markIdx = -1;
void Remove(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].left;
    	HN[DL[i].rh].size--;
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].right;
    	HN[DL[i].rh].size++;
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
void Reduce(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = HN[t].prev;
    HN[HN[t].prev].next = HN[t].next;
    s[DL[i].ch]--;
    DL[DL[i].down].up = DL[i].up;
    DL[DL[i].up].down = DL[i].down;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = DL[k].up;
        DL[DL[k].up].down = DL[k].down;
        s[DL[k].ch]--;
    }
}
void Recover(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = t;
    HN[HN[t].prev].next = t;
    s[DL[i].ch]++;
    DL[DL[i].down].up = i;
    DL[DL[i].up].down = i;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = k;
        DL[DL[k].up].down = k;
        s[DL[k].ch]++;
    }
}
void Select(int i) {
    int s = DL[i].rh;
    HN[HN[s].next].prev = HN[s].prev;
    HN[HN[s].prev].next = HN[s].next;
    Remove(i);
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Remove(j);
    Dep++;
}
void Cancel(int i) {
    int s = DL[i].rh;
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Resume(j);
    Resume(i);    
    HN[HN[s].next].prev = s;
    HN[HN[s].prev].next = s;
    Dep--;
}
int Decision() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        if (s[i] == 1) {
            Select(DL[i].down);
            markStk[++markIdx] = DL[i].down;
            has = 1;
        }
    }
    return has;
}
int Subset(int x, int y) {	// 0: x in y, 1: y in x 
    assert(DL[x].ch == DL[y].ch);
    int a = 0, b = 0;
    int i, j;
    for (i = DL[x].right, j = DL[y].right; i != x && j != y; ) {
        if (DL[i].ch == DL[j].ch)
            i = DL[i].right, j = DL[j].right;
        else if (DL[i].ch < DL[j].ch)
            i = DL[i].right, a = 1;
        else
            j = DL[j].right, b = 1;
        if (a && b)
            break;
    }
    if (i != x)    a = 1;
    if (j != y)    b = 1;
    return a || b ? (a - b) : 1;
}
int Duplicate() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        for (int j = DL[i].down; j != i; j = DL[j].down) {
            for (int k = DL[j].down; k != j && k != i; k = DL[k].down) {
                int cmp = Subset(j, k);
                if (cmp == 0)
                    continue;
                if (cmp == 1) {
                	markStk[++markIdx] = j;
                	Select(j);
            	} else {
            		markStk[++markIdx] = k;
                	Select(k);
                }
                has = 1;
            }
        }
    }
    return has;
}
int H(int limit) {
    static int c, ret, i, j, time = 0;
    static int used[MAXCOL] = {};
    for (c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if (used[c] == time)
        	continue;
    	ret ++, used[c] = time;
    	if (ret >= limit)	return ret;
        for (i = DL[c].down; i != c; i = DL[i].down) {
            for (j = DL[i].right; j != i; j = DL[j].right)
            	used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS() {
    int hval = H(Ans - Dep);
    if (DL[head].right == head && Dep < Ans)
    	Ans = Dep;
    if (Dep + hval >= Ans)
        return ;
    int cover_max = -1, cover_idx = -1;
    for (int i = HN[help_head].next; i != help_head; i = HN[i].next) {
        if (HN[i].size > cover_max) {
            cover_max = HN[i].size;
            cover_idx = HN[i].head;
        }
    }
    
    Select(cover_idx);
    DFS();
    Cancel(cover_idx);
    
    Reduce(cover_idx);
    int markEsp = markIdx;
    while (!Decision() && !Duplicate());
    DFS();
    while (markIdx > markEsp)
        Cancel(markStk[markIdx--]);
    Recover(cover_idx);
}
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 new_row(int n, int Row[], int rh) {
    int r, row = -1, k;
    int h = size;
    for (int i = 0; i < n; i++) {
        r = Row[i];
        DL[size].ch = r, s[r]++;
        DL[size].rh = rh;
        if (row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
        } else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
        }
    }
    HN[rh].size = n;
    HN[rh].head = h;
    HN[rh].next = HN[help_head].next;
    HN[rh].prev = help_head;
    HN[HN[help_head].next].prev = rh;
    HN[help_head].next = rh;
}
void init(int m) {
    size = 0;
    help_head = 0, HN[help_head].next = HN[help_head].prev = help_head;
    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;
        DL[i].rh = 0;	// important pointer (fail pointer)
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
    	int A[MAXN], B[MAXN];
        int toy[10005] = {}, R[MAXCOL];
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &A[i], &B[i]);
            toy[A[i]]++, toy[B[i]]++;
        }
        
        init(n);
        int run_id = 0;
        for (int i = 0; i <= 10000; i++) {
            int nt = 0;
            for (int j = 1; j <= n; j++) {
                if (A[j] == i || B[j] == i)
                    R[nt++] = j;
            }
            if (nt) {
                run_id++;
                new_row(nt, R, run_id);
            }
        }
        Ans = n;
        Dep = 0, markIdx = -1;
        Decision();
        DFS();
        printf("%d\n", Ans);
        fflush(stdout);
    }
    return 0;
}

Morris' Blog