Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem I

Christmas Gifts

Input File: pi.in

Time Limit: 3 seconds

        Children always expect gifts at Christmas Eve. Every child in the community No-Common-Present-Compromise (NCPC for short) can have two wished for toys, and Santa Claus always promises at least one of the two wishes. Children in NCPC are all unselfish such that a toy can be shared by many children. This year, all the wished have been collected and you are asked to help Santa Claus to prepare the gifts for all the children. Due to the limited capacity of the cart, you need to minimize the number of gifts. But remember, for every child, at least one of the two wishes should be satisfied.

        For the example shown in the first test case of the Sample Input, there are four children. The first child wished to have toy 0 or 1, and the toys wished by the other three children are respectively 100 or 1, 100 or 0, and 100 or 200. For this case, you can prepare only two toys (0 and 100) to satisfy all the four children.

 

Technical Specification

1.     Every wish is a toy and labeled by an nonnegative integer at most 10000.

2.     The number n of different toys is at most 250.

3.     The number m of children is a positive integer and at most 5000.

4.     For each test case, n <= 100 or m<= 400.

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

---

這題被學長認定是 NPC 問題, 當下我們都以為匹配可以做到, 或者是某種特殊的解, 我當初傻傻地以為可以轉換成最小費用流, 導致學長浪費一個小時在 coding 最小費用流, 我真的是大錯特錯了。

最狠的測資是
3
1 2
2 3
3 1
這時候匹配是錯誤的, 既然是 NPC 問題, 那麼肯定是 dfs 解, 當下我滿腦子都是 DLX 的最少重複覆蓋, 但是遲遲不敢 coding, 為了加速 dfs 解法, 我想 DLX 是最好的方法。

不過比賽沒有任何人解出這題, 我的解法是否正確也值得探討, 目前只希望有人能驗證我生出的測資的正確性。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxv 100000
#include <set>
using namespace std;
struct DacingLinks {
    int left, right;
    int up, down;
    int data, ch, rh;
}DL[500000];
int s[5001], o[5001], head, size, Ans;
void Remove(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
int used[5001] = {};
int H() {
    static int c, ret, i, j, time = 0;
    for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if(used[c] != time) {
            ret ++, used[c] = time;
            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 k) {
    if(k + H() >= Ans)    return;
    if(DL[head].right == head) {
        if(k < Ans)    Ans = 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;
        }
    }
    for(i = DL[c].down; i != c; i = DL[i].down) {
        Remove(i);
        for(j = DL[i].right; j != i; j = DL[j].right)    Remove(j);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)        Resume(j);
        Resume(i);
    }
}
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 a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        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;
        }
    }
}
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;
    }
}
int main() {
    int n, A[5005], B[5005];
    while(scanf("%d", &n) == 1 && n) {
        set<int> toy;
        int i;
        for(i = 1; i <= n; i++) {
            scanf("%d %d", &A[i], &B[i]);
            toy.insert(A[i]);
            toy.insert(B[i]);
        }
        init(n);
        int Row[5005], nt;
        for(set<int>::iterator it = toy.begin();
            it != toy.end(); it++) {
            nt = 0;
            for(i = 1; i <= n; i++) {
                if(A[i] == *it || B[i] == *it) {
                    Row[nt++] = i;
                }
            }
            new_row(nt, Row);
        }
        Ans = Maxv;
        DFS(0);
        printf("%d\n", Ans);
    }
    return 0;
}
/*
4
0 1
100 1
100 0
100 200
12
10 20
20 30
30 40
40 50
50 60
60 70
70 80
80 10
10 0
30 0
50 0
70 0
3
1 2
2 3
3 1
0
*/