b259. H. 補習班的報名熱＠Morris' Blog｜PChome Online 個人新聞台

2011-09-11 11:10:55| 人氣788| 回應0 | 上一篇 | 下一篇

b259. H. 補習班的報名熱

推薦 0 收藏 0 轉貼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。

範例輸入：

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;
}

我要檢舉

#b259#H #補習班的報名熱

台長： Morris

您可能對以下文章有興趣

d589. B. 水之國的奇幻冒險

[ZJ][翻轉處理] a315. D 滿州國皇帝之璽

[ZJ][KM算法] d210. 老問題

[NPSC][方格法] b256. E. 大風吹

人氣(788) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:d965. E. 阿達的冒險
此分類上一篇:b043. B. 踩地雷回來了

回應(0)