NCPC2012I Christmas Gifts
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.
輸入說明 ：
The input file contains several test cases. For each test case, the first line contains the integer m which is the number of children in this case. In the following m lines, each line contains two integers separated by a space, in which the two integers are the toy labels the child wishes for. A case with m = 0 indicates the end of the input and you don’t need to process it.
輸出說明 ：
For each test case, output in one line the minimum number of gifts that Santa Claus should prepare.
範例輸入 ：
40 1100 1100 0100 2001210 2020 3030 4040 5050 6060 7070 8080 1010 030 050 070 0
範例輸出 ：
2
4
提示 ：
現在先開放 30 秒，測資驗證正確後壓回 3 秒。
有任何問題私信告訴我。
出處 ：
這題被學長認定是 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
*/