uva 11218 - KTV

点击打开链接

题目意思：   有九个人去KTV唱歌，现在进行3个3个的组队，最多有81组，然后每一组会有一个分数，现在要我们找到三组得分最高的输出最高的得分。

解题思路：   1 首先我们应该了解如果同一个人同时在两个组中出现，那么这个就是不符和条件。

                    2 由于n最大为81，那么如果我么吧直接去枚举每一种情况，复杂度就是0(n^3)这个是可以接受的肯定不会超时，所以我么的解题思路就是暴力枚举

                    3 注意我么在枚举的时候只要枚举到满足的组后就将它的三个成员标记为访问过，当这个做完以后还要从新标记为0，进行下一轮的搜索，这个地方我WA了很多次

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <set>
using namespace std;
#define MAXN 85

int a[MAXN] , b[MAXN] , c[MAXN] , s[MAXN];
int vis[10];
int n , cnt , ans;

//初始化
void init(){
    ans = 0;
    memset(a , 0 , sizeof(a));
    memset(b , 0 , sizeof(b));
    memset(c , 0 , sizeof(c));
    memset(s , 0 , sizeof(s));
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    cnt = 1;
    while(scanf("%d" , &n) && n){
        init();
        for(int i = 0 ; i < n ; i++)
            scanf("%d%d%d%d" , &a[i],&b[i],&c[i],&s[i]);
        for(int i = 0 ; i < n ; i++){
            vis[a[i]] = vis[b[i]] = vis[c[i]] = 1;//标记为1
            for(int j = 0 ; j < n ; j++){
                if(i == j) continue;
                if(vis[a[j]] || vis[b[j]] || vis[c[j]]) continue;
                vis[a[j]] = vis[b[j]] = vis[c[j]] = 1;//标记为1
                for(int k = 0 ; k < n ; k++){
                    if(k == i || k == j) continue;
                    if(vis[a[k]] || vis[b[k]] || vis[c[k]]) continue;
                    if(ans < s[i]+s[j]+s[k]) ans = s[i]+s[j]+s[k];
                }
                vis[a[j]] = vis[b[j]] = vis[c[j]] = 0;//从新标记为0
            }
            vis[a[i]] = vis[b[i]] = vis[c[i]] = 0;//从新标记为0
        }
        if(ans == 0) printf("Case %d: -1\n" , cnt++);
        else  printf("Case %d: %d\n" , cnt++ , ans);
    }  
    return 0;
}