Problem K

KTV

解题思路：题目的意思是说9个人平均分成三组，题目的输出提供分组的情况，每组有一个权值，在找到三组刚好是不同9个人的前提下求出最大的权值，如果连一种找齐的情况都没有则输出-1，所以就直接一层一层以两个分支往下查找就行了

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=112&page=show_problem&problem=2159

1 #include
     
       2 #include
      
        3 #include
       
         4 #define SIZE 81 5 using namespace std; 6 typedef struct group{ 7     int member[3]; 8     int score;     9 }group;10 int n, score;11 group Case[SIZE];12 int ktv[10], list[3];13 14 void Traverse(int cur, int cnt){15     if(cur >= n || cnt == 3){16         if(cnt == 3){17             int sum = 0;18             for(int i=0; i<3; ++i){19                 sum += Case[list[i]].score;20             }21             if(sum > score) score = sum;22         }23         return;24     }25     bool flag = false;26     for(int i=0; i<3; ++i){27         if(ktv[Case[cur].member[i]] == 1){28             flag = true;29             break;30         }31     }32     if(!flag){33         for(int i=0; i<3; ++i){34             ktv[Case[cur].member[i]] = 1;35         }36         list[cnt] = cur;37         Traverse(cur+1, cnt+1);38         for(int i=0; i<3; ++i){39             ktv[Case[cur].member[i]] = 0;40         }41     }42     Traverse(cur+1, cnt);43     return;44 }45 46 int main()47 {48     #ifndef ONLINE_JUDGE49     freopen("input.txt", "r", stdin);50     #endif51     int T = 0;52     while(cin>>n && n){53         score = -1;54         memset(ktv, 0, sizeof(ktv));55         for(int i=0; i
        
         >Case[i].member[j];58             }59             cin>>Case[i].score;60         }61         Traverse(0, 0);62         cout<<"Case "<<++T<<": "<
         
          <