Uva 11218 KTV

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<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 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_JUDGE
49     freopen("input.txt", "r", stdin);
50     #endif
51     int T = 0;
52     while(cin>>n && n){
53         score = -1;
54         memset(ktv, 0, sizeof(ktv));
55         for(int i=0; i<n; ++i){
56             for(int j=0; j<3; ++j){
57                 cin>>Case[i].member[j];
58             }
59             cin>>Case[i].score;
60         }
61         Traverse(0, 0);
62         cout<<"Case "<<++T<<": "<<score<<endl;
63     }        
64     return 0;
65 }