[UVa] 11218 KTV.cpp

#include <cstdio>
#include <cstring>

struct Combination{
    unsigned int bit;
    int score;
};
Combination C[100];
int dp[1<<9];

void dfs(int, unsigned int, int);
bool CombineCheck(unsigned int, unsigned int);

int main()
{
    int N, a, b, c, s, Case = 1;
    while (scanf("%d", &N) && N) {
        // Input
        for (int i = 0; i < N; ++i) {
            scanf("%d %d %d %d", &a, &b, &c, &s);
            C[i].bit = (unsigned int)0 | (1<<(a-1)) | (1<<(b-1)) | (1<<(c-1));
            C[i].score = s;
        }

        // dfs for every possible combination
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; ++i)
            dfs(N, C[i].bit, C[i].score);

        // Output
        printf("Case %d: ", Case++);
        if (dp[(1<<9)-1] == 0) puts("-1");
        else printf("%d\n", dp[(1<<9)-1]);
    }
}
void dfs(int N, unsigned int bit, int score)
{
    for (int i = 0; i < N; ++i) {
        if (CombineCheck(bit, C[i].bit)) {
            unsigned int combined_bit = bit | C[i].bit;
            if (dp[combined_bit] < score + C[i].score) {
                dp[combined_bit] = score + C[i].score;
                dfs(N, combined_bit, dp[combined_bit]);
            }
        }
    }
}
bool CombineCheck(unsigned int a, unsigned int b)
{
    unsigned int c = a | b;
    int numA = 0, numB = 0, numC = 0;
    for (int i = 0; i < 9; ++i) {
        if (a & (1<<i)) ++numA;
        if (b & (1<<i)) ++numB;
        if (c & (1<<i)) ++numC;
    }
    return numA + numB == numC;
}