[搜索]USACO Open05 疾病管理 disease 解題報告

Title: 疾病管理

Input: disease.in

Output: disease.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】

天啊，真是不幸！最近在農夫 John 的農場上有 D(1<=D<=15) 種疾病 ( 疾病的編號為 1..D) 在奶牛當中流行。 John 想要給他的 N(1<=N<=1000) 頭奶牛擠牛奶。擠出來的牛奶都被放在一個罐子裡面。如果這些牛奶中包含了超過 K(1<=K<=D) 種的疾病，那麼這些牛奶就要全部被丟棄掉了（浪費啊 -_-! ）。 John 應該給這 N 頭奶牛當中的哪些奶牛擠奶，才能使得牛奶不被丟棄，並且擠牛奶的數量最多呢？

 

【輸入格式】

第一行：三個整數 N,D 和 K

接下來有 N 行：這當中的第 i 行描述了第 i 個奶牛得病的資訊。第一個數字 p ，表示第 i 頭奶牛得了 p 種病，接下來有 p 個數字表示這些病的編號。如果 p 等於 0 ，表明這頭奶牛很健康。

【輸出格式】

輸出 John 最多可以給多少頭奶牛擠牛奶。

【輸入輸出樣例】

輸入:

6 3 2

0

1 1

1 2

1 3

2 2 1

2 2 1

輸出:

5

【輸入輸出樣例說明】

John 最多可以給 5 頭奶牛擠牛奶。他們的編號分別為 1,2,3,5,6. 此時這些牛奶中只包含 2 種疾病，編號為 1 ， 2 。疾病種數不超過 K=2.

【分析】

赤裸裸的搜索題～有D種疾病，所以一共有2^D種『疾病搭配方案』。

所以，用DFS構造一個二叉的搜索樹，對於每種疾病都有兩種狀態：要或者不要。

由於題目上說“最多”，所以一定要把K種疾病都『用』上，這樣可以得到最優解。

每得到一種『疾病搭配方案』，就要遍歷N頭奶牛，把符合這個『疾病方案』的奶牛個數統計出來即可。

我想到一個優化，在讀入時，如果一頭奶牛有K+1(或以上)種疾病，則直接忽略；如果一頭奶牛沒有病，則直接選上即可，也不用參與接下來的搜索判斷。

這個算法+優化還是挺高效的，10組數據一共0.030秒，比我們學校第二快的那位童鞋的程序還要快4倍～

Code！！

【我的代碼】

裸代碼RawCode

C++语言: Codee#25453

001 /*
002 *Problem: USACO Open05 Disease Management
003 *Author: Yee-fan Zhu
004 *Method: DFS
005 *E-mail: zyfworks@gmail.com
006 */
007 #include <cstdio>
008 #include <cstdlib>
009 #include <cstring>
010 #define openfile(str) freopen(str".in","r",stdin),freopen
011
012 (str".out","w",stdout)
013 using namespace std;
014 const int MAXN=1001;
015 class Cow
016 {
017 public:
018     int Num;
019     int Dis[16];
020     void Clear()
021     {
022         Num=0;
023     }
024 }C[MAXN];
025
026 int Dz[16]={0};
027 int Now=0;
028 int Ans=0;
029 int Top=0;
030
031 int N,D,K;
032
033 void init()
034 {
035     scanf("%d %d %d\n",&N,&D,&K);
036     int n,tmp;
037     for(int i=1;i<=N;i++)
038     {
039         scanf("%d",&n);
040         if(n==0)
041         {
042             Now++;
043             continue;
044         }
045         if(n>K)
046         {
047             for(int j=1;j<=n;j++)
048                 scanf("%d",&tmp);
049             continue;
050         }
051         Top++;
052         C[Top].Clear();
053         C[Top].Num=n;
054         for(int j=1;j<=n;j++)
055             scanf("%d",&C[Top].Dis[j]);
056     }
057     memset(Dz,0,sizeof(Dz));
058 }
059
060 void check()
061 {
062     bool flag;
063     int res=0;
064     for(int i=1;i<=Top;i++)
065     {
066         flag=true;
067         for(int j=1;j<=C[i].Num;j++)
068         {
069             if(Dz[C[i].Dis[j]]==0)
070             {
071                 flag=false;
072                 break;
073             }
074         }
075         if(flag)
076             res++;
077     }
078     if(res>Ans)
079         Ans=res;
080 }
081
082 void dfs(int x,int d)
083 {
084     if(x==D+1)
085     {
086         if(d==K)
087             check();
088         return;
089     }
090     dfs(x+1,d);
091     Dz[x]=1;
092     dfs(x+1,d+1);
093     Dz[x]=0;
094     return;
095 }
096
097 int main()
098 {
099     openfile("disease");
100     init();
101     dfs(1,0);
102     printf("%d\n",Ans+Now);
103     return 0;
104 }