2011-09-11 11:10:55Morris
b259. H. 補習班的報名熱
b259. H. 補習班的報名熱
作法 : 精準覆蓋問題
原本是想用 DP 去解的, 精準覆蓋問題, 其實只是 DFS 的優化而已,
以下採用了 dancing links, 剛好測資頗弱的, 秒速極少
/**********************************************************************************/
/* Problem: b259 "H. 補習班的報名熱" from 2009 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC(16ms, 796KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 11:00:58 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Swap(x, y) {int t; t = x, x = y, y = t;}
#define Maxv 100000
struct DacingLinks {
int left, right;
int up, down;
int data, ch, rh;
}DL[20001];
int s[1001], o[1001], head, len, size, flag;
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(flag > 1) return;
if(DL[head].right == head) {
flag++, 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 new_row(int n, int Row[], int i) {
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 = i;
}else {
k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
DL[k].rh = i;
}
}
}
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;
}
}
typedef struct {
int A, B;
}Data;
Data in[10001], out[10001];
int cmp(const void *a, const void *b) {
Data *aa, *bb;
aa = (Data *)a, bb = (Data *)b;
if(bb->A < aa->A) return 1;
return 0;
}
main() {
int n, m, a, b, Row[2], T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
init(n);
for(a = 1; a <= m; a++) {
scanf("%d %d", &Row[0], &Row[1]);
if(Row[0] > Row[1])
Swap(Row[0], Row[1]);
in[a].A = Row[0], in[a].B = Row[1];
new_row(2, Row, a);
}
len = Maxv, flag = 0, DFS(0);
if(flag == 1) {
printf("YES\n");
for(a = 0; a < len; a++)
out[a] = in[DL[o[a]].rh];
qsort(out, len, sizeof(Data), cmp);
for(a = 0; a < len; a++)
printf("%d %d\n", out[a].A, out[a].B);
}
else puts("NO");
}
return 0;
}
內容 ：
近
年來，由於各式各樣的升學壓力，幾乎很多家長們都會把孩子送到補習班裡面去學習，增加孩子們的競爭力。當然，今年也不例外。NPSC (Nobel
Prize So Cool)
就是在這樣的環境底下成立的一個補習班。它打著培養孩子們發展科學和資訊能力結合的潛力，美其名『諾貝兒程式設計練才專班』，實際上卻是專門招收有才華的
學生把他們組成一隊一隊的送進NPSC來比賽的可怕組織。
當然，經營了兩、三年後，經歷了各式各樣口碑的考驗，成功在補習業界闖出一片天。隨著大家口耳相傳，來報名的家長和孩子們也越來越多，今年甚至有多達近萬
名的家長帶著學生來報名。因此，NPSC為了應付如此龐大的報名熱潮，做出了以下三點規範：
其一，今年特別規劃『家長排隊區』專門讓家長們排隊，如此一來孩子們便可以省下排隊的時間，專心寫程式。
其二，每一位家長必須一次幫兩位孩子報名，因為這樣補習班才能夠收到兩份的報名費用。如果出現了重複報名的現象，就視同報名失敗。
其三，如果報名失敗了，本年度將不得再度報名。
在某間高中的程式設計社裡面，有N個成員，他們決定今年一起報名NPSC，目標是打進決賽。於是他們找了M個路人，打算請這些路人幫忙排隊報名。不過為了
避免有人報不到名，或者重複報名，每個路人都只會幫兩個成員排隊。你很湊巧地，是這個程式設計社當中的副社，而這個社團的社長早就已經寫ACM寫到完全忘
我的境界了，重責大任於是落在你的身上。因此你很想知道，是不是真的能夠從這M個路人中請一些人出來排隊，最終能夠讓所有的N名成員都成功地報名了
NPSC練才專班。你很開心地寫了一個程式讓它放著慢慢跑，然後開心地跑去睡覺了。 不過你做了一個夢。
在夢境中，費盡了千辛萬苦，終於，從這M個路人裡面挑了一些人請他們幫忙排隊報名。但是，這些人裡面有人卻出現了不平之鳴。「為什麼是我要排隊？」「我比
較想在家裡看電視啦！」「早知道就不幫忙出主意了！」「如果我沒有幫忙的話，明明有別種方案的啊，為什麼要找我！」 你驚醒。
你快速地檢查了程式，它還在慢跑，一點回應也沒有。你擔心，如果除了從這M個路人中找出某些人幫忙以外，如果還存在著另外一種讓N名成員都報名成功的方
案，那麼這些人可能會吵架，會壞了大事的，因此這樣的報名方案不算是順利完成。換句話說，就像是３６＋４５＝７９一樣，如果解法不是唯一的，那麼勢必會有
很多人感到新奇、溫馨、誇張、難過、實用、高興、無聊，或者生氣。 「這真是個盲點呀華生！」
你大夢初醒。決定趕快生出一份程式，判斷到底有沒有辦法從這M個路人裡面唯一地找出一些人讓他們可以很順利地幫社團全部的N名成員完成報名呢？
輸入說明
：
輸
入的第一行包含一個正整數T代表測試資料的筆數。 接下來的每一筆測試資料，其第一行包含兩個正整數N,
M依序代表社團的人數和路人的個數(1<=N<=1000, 0<=M<=10000)。而社團當中的成員也被編號為1, 2,
…, N。 接下來有M行，每一行有兩個數字Ai,
Bi，代表第i個路人想要幫社團裡面編號為Ai和Bi的兩名成員一起報名補習班。對於所有的i，Ai不會等於Bi。
輸出說明
：
對
於每一筆測試資料，如果不管怎麼挑路人都無法達成目標的話，請輸出NO。否則請輸出YES，而且要輸出那唯一的一種報名方案。
每一行輸出以一個空白隔開的兩個數字a, b(其中a<b)，代表有某個路人會幫編號為a,
b的兩名成員一起報名。請將這些數對由小到大輸出，也就是說，如果a, b比c, d還要早輸出，那麼一定有a < c。
範例輸入
：
2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
3 4
範例輸出 ：
NO YES 1 2 3 4
提示
：
出處
：
2009 NPSC 高中組決賽
作法 : 精準覆蓋問題
原本是想用 DP 去解的, 精準覆蓋問題, 其實只是 DFS 的優化而已,
以下採用了 dancing links, 剛好測資頗弱的, 秒速極少
/**********************************************************************************/
/* Problem: b259 "H. 補習班的報名熱" from 2009 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC(16ms, 796KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 11:00:58 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Swap(x, y) {int t; t = x, x = y, y = t;}
#define Maxv 100000
struct DacingLinks {
int left, right;
int up, down;
int data, ch, rh;
}DL[20001];
int s[1001], o[1001], head, len, size, flag;
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(flag > 1) return;
if(DL[head].right == head) {
flag++, 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 new_row(int n, int Row[], int i) {
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 = i;
}else {
k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
DL[k].rh = i;
}
}
}
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;
}
}
typedef struct {
int A, B;
}Data;
Data in[10001], out[10001];
int cmp(const void *a, const void *b) {
Data *aa, *bb;
aa = (Data *)a, bb = (Data *)b;
if(bb->A < aa->A) return 1;
return 0;
}
main() {
int n, m, a, b, Row[2], T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
init(n);
for(a = 1; a <= m; a++) {
scanf("%d %d", &Row[0], &Row[1]);
if(Row[0] > Row[1])
Swap(Row[0], Row[1]);
in[a].A = Row[0], in[a].B = Row[1];
new_row(2, Row, a);
}
len = Maxv, flag = 0, DFS(0);
if(flag == 1) {
printf("YES\n");
for(a = 0; a < len; a++)
out[a] = in[DL[o[a]].rh];
qsort(out, len, sizeof(Data), cmp);
for(a = 0; a < len; a++)
printf("%d %d\n", out[a].A, out[a].B);
}
else puts("NO");
}
return 0;
}
上一篇：b043. B. 踩地雷回來了
下一篇：d965. E. 阿達的冒險