uva 11218 - KTV 简单回溯

   感觉有比回溯更加高效的方法，但是水平不够，只会回溯

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
bool h[10]={0};
int Max;
struct node
{
    int a,b,c,s;
}org[82];
void dfs(int r,int i,int now)
{
    if(!r)
    {
        Max=max(Max,now);
        return;
    }
    for(--i;i>=0;i--)
    {
        if(h[org[i].a]||h[org[i].b]||h[org[i].c])continue;
        h[org[i].a]=h[org[i].b]=h[org[i].c]=1;
        dfs(r-1,i,now+org[i].s);
        h[org[i].a]=h[org[i].b]=h[org[i].c]=0;
    }
    return;
}
int main()
{
    int n,i,C=0;
    while(~scanf("%d",&n)&&n)
    {
        Max=-1;
        for(i=0;i<n;i++)
            scanf("%d%d%d%d",&org[i].a,&org[i].b,&org[i].c,&org[i].s);
        dfs(3,n,0);
        printf("Case %d: %d\n",++C,Max);
    }
}