求极大团数量

那种做的时候不知道为什么错,不知道为什么对,不知道为什么超时的题目

题目:http://poj.org/problem?id=2989

All Friends

Problem Description

Sociologists are interested in the phenomenon of "friendship". To study this property, they analyze various groups of people. For each two persons in such a group they determine whether they are friends (it is assumed that this relation is symmetric). The sociologists are mostly interested in the sets of friends. The set S of people is the set of friends if every two persons in S are friends. However, studying the sets of friends turns out to be quite complicated, since there are too many such sets. Therefore, they concentrate just on the maximal sets of friends. A set of friends S is maximal if every person that does not belong to S is not a friend with someone in S. Your task is to determine the number of maximal sets of friends in each group. In case this number exceeds 1 000, you just need to report this -- such a group is too complicated to study. 

Input

The input consists of several instances, separated by single empty lines. The first line of each instance consists of two integers 1 ≤ n ≤ 128 and m -- number of persons in the group and number of friendship relations. Each of m following lines consists of two integers ai and bi (1 ≤ ai, bi ≤ n). This means that persons ai and bi (ai ≠ bi) are friends. Each such relationship is described at most once. 

Output

The output for each instance consists of a single line containing the number of maximal sets of friends in the described group, or string "Too many maximal sets of friends." in case this number is greater than 1 000. 

Sample Input

5 4 1 2 3 4 2 3 4 5

Sample Output

4

代码:http://paste.ubuntu.com/7488676/

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1006.cpp
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 128, M = 1e3, Bit = 64;
struct node {
    long long x, y;
    node(long long tx = 0, long long ty = 0) {
        x = tx, y = ty;
    }
    node operator| (const node &t) const {
        node ret;
        ret.x = x | t.x, ret.y = y | t.y;
        return ret;
    }
    node operator& (const node &t) const {
        node ret;
        ret.x = x & t.x, ret.y = y & t.y;
        return ret;
    }
    bool operator== (const node &t) const {
        return (x == t.x) && (y == t.y);
    }
} f[N + 5], ept[N + 5], mat[N + 5];
int ans, n;
node exchange(int size) {
    node ret;
    long long t = 1;
    if (size < Bit) ret.x = t << size;
    else ret.y = t << (size - Bit + 1);
    return ret;
}
void Dfs(int cur, node pre, node next) {
    if (ans > M) return;
    if (pre == next) {
        ++ans;
        return;
    }
    for (int i = 0; i < cur; ++i)
        if ((next & ept[i]) == ept[i] && (ept[i] & pre) == node(0,0) && (f[cur] & next) == (mat[i] & f[cur] & next)) return;
    for (int i = cur + 1; i < n; ++i)
        if ((next & ept[i]) == ept[i]) Dfs(i, pre | ept[i], next & mat[i]);
    return;
}
void Solve() {
    ans = 0;
    for (int i = 0; i < n; ++i)
        if (ans > M) break;
        else Dfs(i, ept[i], mat[i]);
    if (ans > M) printf(“Too many maximal sets of friends.\n”);
    else printf(“%d\n”, ans);
    return;
}
int main() {
    for (int i = 0; i < N; ++i) f[i] = ept[i] = exchange(i);
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < N; ++j) f[i] = f[i] | ept[j];
    int m;
    while (scanf(“%d%d”, &n, &m) != EOF) {
        for (int i = 0; i < N; ++i) mat[i] = ept[i];
        while (m–) {
            int u, v;
            scanf(“%d%d”, &u, &v);
            –u, –v;
            mat[u] = mat[u] | ept[v], mat[v] = mat[v] | ept[u];
        }
        Solve();
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/2795 - 海胖博客