2011-09-11 11:10:55Morris

b259. H. 補習班的報名熱

b259. H. 補習班的報名熱

內容 :

近 年來,由於各式各樣的升學壓力,幾乎很多家長們都會把孩子送到補習班裡面去學習,增加孩子們的競爭力。當然,今年也不例外。NPSC (Nobel Prize So Cool) 就是在這樣的環境底下成立的一個補習班。它打著培養孩子們發展科學和資訊能力結合的潛力,美其名『諾貝兒程式設計練才專班』,實際上卻是專門招收有才華的 學生把他們組成一隊一隊的送進NPSC來比賽的可怕組織。  當然,經營了兩、三年後,經歷了各式各樣口碑的考驗,成功在補習業界闖出一片天。隨著大家口耳相傳,來報名的家長和孩子們也越來越多,今年甚至有多達近萬 名的家長帶著學生來報名。因此,NPSC為了應付如此龐大的報名熱潮,做出了以下三點規範:  其一,今年特別規劃『家長排隊區』專門讓家長們排隊,如此一來孩子們便可以省下排隊的時間,專心寫程式。 其二,每一位家長必須一次幫兩位孩子報名,因為這樣補習班才能夠收到兩份的報名費用。如果出現了重複報名的現象,就視同報名失敗。 其三,如果報名失敗了,本年度將不得再度報名。  在某間高中的程式設計社裡面,有N個成員,他們決定今年一起報名NPSC,目標是打進決賽。於是他們找了M個路人,打算請這些路人幫忙排隊報名。不過為了 避免有人報不到名,或者重複報名,每個路人都只會幫兩個成員排隊。你很湊巧地,是這個程式設計社當中的副社,而這個社團的社長早就已經寫ACM寫到完全忘 我的境界了,重責大任於是落在你的身上。因此你很想知道,是不是真的能夠從這M個路人中請一些人出來排隊,最終能夠讓所有的N名成員都成功地報名了 NPSC練才專班。你很開心地寫了一個程式讓它放著慢慢跑,然後開心地跑去睡覺了。  不過你做了一個夢。 在夢境中,費盡了千辛萬苦,終於,從這M個路人裡面挑了一些人請他們幫忙排隊報名。但是,這些人裡面有人卻出現了不平之鳴。「為什麼是我要排隊?」「我比 較想在家裡看電視啦!」「早知道就不幫忙出主意了!」「如果我沒有幫忙的話,明明有別種方案的啊,為什麼要找我!」  你驚醒。  你快速地檢查了程式,它還在慢跑,一點回應也沒有。你擔心,如果除了從這M個路人中找出某些人幫忙以外,如果還存在著另外一種讓N名成員都報名成功的方 案,那麼這些人可能會吵架,會壞了大事的,因此這樣的報名方案不算是順利完成。換句話說,就像是36+45=79一樣,如果解法不是唯一的,那麼勢必會有 很多人感到新奇、溫馨、誇張、難過、實用、高興、無聊,或者生氣。  「這真是個盲點呀華生!」  你大夢初醒。決定趕快生出一份程式,判斷到底有沒有辦法從這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;
}