One song is extremely popular recently, so you and your friends decided to sing it in KTV. The song has 3 characters, so exactly 3 people should sing together each time (yes, there are 3 microphones in the room). There are exactly 9 people, so you decided that each person sings exactly once. In other words, all the people are divided into 3 disjoint groups, so that every person is in exactly one group.

However, some people don‘t want to sing with some other people, and some combinations perform worse than others combinations. Given a score for every possible combination of 3 people, what is the largest possible score for all the 3 groups?

Input

Output

Sample Input

3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0

Output for the Sample Input

Case 1: 6
Case 2: -1

一道非常简单的回溯搜索题目。

题意：最近有一首三人合唱的歌很流行，你与朋友共九个人一同到KTV欢唱，你们决定一人只能唱一次，也就是将九个人分成三组，一组三人，每人刚好都被分派到一个组别。但是有些人并不喜欢与另一些人搭档，而有些组合的效果并不好听，所以我们对所有可能的三人组合打分数，请找出9人最高的分组分数总和。

#include<iostream>
#include<cstring>

using namespace std;

int vis[15],arry[100];
int cost,tag,m;

class State
{
public:
    int x,y,z,val;
}st[100];

bool ok()
{
    for(int i=1;i<=9;i++)
        if(!vis[i]) return false;
    return true;
}

void dfs(int pos,int value)
{
    if(ok())
    {
        tag=1;
        if(value>cost) cost=value;
        return;
    }
    int i,j,k;
    for(i=0;i<m;i++)
    {
        if(arry[i]==0&&vis[st[i].x]==0&&vis[st[i].y]==0&&vis[st[i].z]==0)
        {
            arry[i]=1;
            vis[st[i].x]=vis[st[i].y]=vis[st[i].z]=1;
            dfs(i,value+st[i].val);
            arry[i]=0;
            vis[st[i].x]=vis[st[i].y]=vis[st[i].z]=0;
        }
    }
}

int main()
{
    int k=0;
    while(cin>>m&&m)
    {
        tag=0,cost=0;
        memset(vis,0,sizeof(vis));
        memset(arry,0,sizeof(arry));
        for(int i=0;i<m;i++)
            cin>>st[i].x>>st[i].y>>st[i].z>>st[i].val;
        for(int i=0;i<m;i++)
        {
            arry[i]=1;
            vis[st[i].x]=vis[st[i].y]=vis[st[i].z]=1;
            dfs(i,st[i].val);
            arry[i]=0;
            vis[st[i].x]=vis[st[i].y]=vis[st[i].z]=0;
        }
        cout<<"Case "<<++k<<": ";
        if(tag==0) cout<<"-1"<<endl;
        else cout<<cost<<endl;
    }
    return 0;
}

[回溯]KTV uva11218

原文：http://blog.csdn.net/zju_ziqin/article/details/19108101