uva 219-Department of Redundancy Department(dfs+枝切り)

タイトルリンク:uva 219-Department of Redundancy Department
いくつかの関系を与えて、どの関系が取って代わることができることを闻いて、もし取って代わることができるならば、取って代わる方案を与えて、1种でいいです.
解題構想:全部で26文字なので、状態をバイナリ数で表します.枝を切り、すべてのオプション関係を考慮するたびに満足できないのがfalseです.

#include 
#include 
#include 

using namespace std;
const int maxn = 105;

bool flag;
int n, l[maxn], r[maxn];
int cnt, ans[maxn], v[maxn];

inline void cat (char* str, int x) {
    bool sign = false;
    int len = strlen(str);

    for (int i = 0; i < len; i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') {
            if (sign)
                r[x] |= (1<'A'));
            else
                l[x] |= (1<'A'));
        } else
            sign = true;
    }
}

inline void init () {
    char str[maxn];
    flag = true;
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));

    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        cat(str, i);
    }
}

inline void put (int k) {
    printf("     FD %d is redundant using FDs:", k + 1);
    for (int i = 0; ans[i] != -1; i++)
        printf(" %d", ans[i]);
    printf("
");
}

bool check (int s, int k) {
    int vis[maxn];
    memset(vis, 0, sizeof(vis));

    while (true) {
        bool stop = true;
        for (int i = 0; i < n; i++) {
            if (vis[i] || v[i])
                continue;

            if ((s & l[i]) != l[i])
                continue;

            vis[i] = 1;
            s |= r[i];
            stop = false;
        }

        if (stop)
            break;
    }

    return (s | r[k]) != s;
}

bool dfs (int d, int s, int k) {
    ans[d] = -1;

    if ((s & r[k]) == r[k])
        return true;

    if (check(s, k))
        return false;

    for (int i = 0; i < n; i++) {
        if (v[i])
            continue;

        if ((s & l[i]) != l[i])
            continue;

        if ((s | r[i]) == s)
            continue;

        v[i] = 1;
        if (dfs(d, s, k))
            return true;

        ans[d] = i + 1;
        if (dfs(d+1, s | r[i], k))
            return true;
        v[i] = 0;
    }
    return false;
}

void solve () {
    for (int i = 0; i < n; i++) {
        memset(v, 0, sizeof(v));
        v[i] = 1;
        if (dfs(0, l[i], i)) {
            put(i);
            flag = false;
        }
    }
}

int main () {
    int cas = 1;
    while (scanf("%d", &n) == 1 && n) {
        init();

        printf("Set number %d
", cas++);
        solve();
        if (flag)
            printf("     No redundant FDs.
");
        printf("
");
    }
    return 0;
}