b040. E. 魔法部的任務＠Morris' Blog｜PChome Online 個人新聞台

2011-11-12 23:10:06| 人氣655| 回應0 | 上一篇 | 下一篇

b040. E. 魔法部的任務

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

傳
說中，魔法部是個處理世界上各種魔法事件的神秘部門，他們的職責就是要保護魔法世界的隱密性，不要讓魔法干擾麻瓜們（魔法世界對不懂魔法的凡人的稱呼）的
生活。身為剛上任的魔法部長，你最近真是忙得焦頭爛額，因為「那個人」回來了（指的是黑魔王佛地魔，因為這個名字實在是太邪惡了，因此大家都以「那個人」
來稱呼他）！由於復活之後的「那個人」開始帶領食死人們在世界上到處作亂，讓你大傷腦筋。還好，你最近得到了一個魔法寶物──「預言之石」，它可以在當天
凌晨零時的時候預言出今天一天之內發生的魔法事件，於是你就可以即時安排正氣師去阻止食死人的行動。
由
於「那個人」不斷的在麻瓜世界裡作亂，因此正氣師得跑到麻瓜世界理去處理，所以就不能騎著掃把到處飛了（要不然被麻瓜們看到就糟糕了）。因此，他們只好學
著使用麻瓜世界的行動方式──開車。還好麻瓜世界的馬路是由一條條南北向的大道和東西向的街組成，就像棋盤一樣，因此每個路口都可以用兩個數字 (x, y) 表示，例如 (5, 3) 就代表第 5 大道第 3 街口。雖然不能騎掃把，正氣師還是可以用一點小小的魔法讓路上通行無阻，因此只要用一分鐘的時間就可以從一個路口到下一個路口，例如從 (5, 3) 開車到 (5, 4) 只要一分鐘就好了；而若是從 (5, 3) 開車到 (7, 5)，則需要 (7-5) + (5-3) = 4 分鐘。
每
當一個魔法事件發生時，都得要有一位正氣師即時趕到才能處理（當然正氣師也可以提早到達發生地點，不過得等到事件發生才能處理）。如果這個正氣師是直接從
正氣師局動身的話，就可以用「現影術」瞬間移動到魔法事件發生的地點。而當正氣師處理完一件事的時候，如果趕得及，還可以再趕去處理另一個魔法事件，這時
就只能開車了（當然，他們隨時都有辦法弄來一部車）。但是最近的事情實在是太多了，讓正氣師局的人員都接應不暇，因此你得作最好的指派，使得可以出最少的
人力去處理完所有的魔法事件。

輸入說明：

輸入資料的第一行有一個數字 n，表示你現在要處理 n 天的資料。每天的資料有許多行，第一行有個數字 m（1 ≤ m ≤ 1000），表示當天預言之石預告了 m 個魔法事件的發生。接下來有 m 行，每行有三個數字 t x y，表示在當天時間 t（0 ≤ t < 1440）的時候在第 x 大道第 y 街口（0 ≤ x, y ≤ 1000）會有魔法事件發生。你可以假設任兩個魔法事件不可能在同時同地發生。

輸出說明：

輸出資料應該有 n 行，每行對應到輸入資料的每一天。每行有一個數字，表示當天最少要派出多少正氣師，才能處理完所有事件。

範例輸入：

範例輸出：

2
1

提示：

出處：

 
  2005 NPSC 高中組初賽

作法 : 將問題轉換成 DAG, 再用最少路徑覆蓋問題去解決它
此作法需要求最大匹配數

/**********************************************************************************/
/* Problem: b040 "E. 魔法部的任務" from 2005 NPSC 高中組初賽          */
/* Language: C (1170 Bytes)                                                      */
/* Result: AC(112ms, 4.2MB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2011-11-12 20:25:59                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
   int x, y, v;
}Path;
Path D[1001];
int cmp(const void *i, const void *j) {
   Path *a, *b;
   a = (Path *)i, b = (Path *)j;
   return a->v - b->v;
}
int map[1002][1002], Mt[1002];
char used[1002];
int mx[1002], my[1002];
int DFS(int now) {
   int a, i;
   for(a = 0; a < Mt[now]; a++) {
       i = map[now][a];
       if(!used[i]) {
           used[i] = 1;
           if(my[i] == 0 || DFS(my[i])) {
               mx[now] = i, my[i] = now;
               return 1;
           }
       }
   }
   return 0;
}
int main() {
   int T;
   scanf("%d", &T);
   while(T--) {
       int n, i, j;
       scanf("%d", &n);
       for(i = 0; i < n; i++) {
            scanf("%d %d %d", &D[i].v, &D[i].x, &D[i].y);
       }
        memset(mx, 0, sizeof(mx));
       memset(my, 0, sizeof(my));
       memset(Mt, 0, sizeof(Mt));
       qsort(D, n, sizeof(Path), cmp);
       for(i = 0; i < n; i++)
           for(j = i+1; j < n; j++)
                if(abs(D[i].x-D[j].x)+abs(D[i].y-D[j].y) <= D[j].v-D[i].v)
                    map[i][Mt[i]++] = j;
       int Ans = 0;
       for(i = 0; i < n; i++)
           if(!mx[i]) {
               memset(used, 0, sizeof(used));
               if(DFS(i))
                   Ans++;
           }
       printf("%d\n", n - Ans);
   }
   return 0;
}

我要檢舉

#b040#E. 魔法部的任務

台長： Morris

您可能對以下文章有興趣

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

b207. F. 世界盃

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

b046. E. 智慧型單字查詢

人氣(655) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[NPSC][2006 高中組][B.古力德] 最小覆蓋圓
此分類上一篇:d965. E. 阿達的冒險

回應(0)