6.1 最大团
//最大团 //返回最大团大小和一个方案,传入图的大小 n 和邻接阵 mat //mat[i][j]为布尔量 #define MAXN 60 void clique(int n, int* u, int mat[][MAXN], int size, int& max, int& bb, int* res, int* rr, int* c) { int i, j, vn, v[MAXN]; if (n) { if (size + c[u[0]] <= max) return; for (i = 0; i < n + size - max && i < n; ++ i) { for (j = i + 1, vn = 0; j < n; ++ j) if (mat[u[i]][u[j]]) v[vn ++] = u[j]; rr[size] = u[i]; clique(vn, v, mat, size + 1, max, bb, res, rr, c); if (bb) return; } } else if (size > max) { max = size; for (i = 0; i < size; ++ i) res[i] = rr[i]; bb = 1; } } int maxclique(int n, int mat[][MAXN], int *ret) { int max = 0, bb, c[MAXN], i, j; int vn, v[MAXN], rr[MAXN]; for (c[i = n - 1] = 0; i >= 0; -- i) { for (vn = 0, j = i + 1; j < n; ++ j) if (mat[i][j]) v[vn ++] = j; bb = 0; rr[0] = i; clique(vn, v, mat, 1, max, bb, ret, rr, c); c[i] = max; } return max; }
6.2 最大团(n<64)(faster)
/** * WishingBone's ACM/ICPC Routine Library * * maximum clique solver */ #include <vector> using std::vector; // clique solver calculates both size and consitution of maximum clique // uses bit operation to accelerate searching // graph size limit is 63, the graph should be undirected // can optimize to calculate on each component, and sort on vertex degrees // can be used to solve maximum independent set class clique { public: static const long long ONE = 1; static const long long MASK = (1 << 21) - 1; 76 char* bits; int n, size, cmax[63]; long long mask[63], cons; // initiate lookup table clique() { bits = new char[1 << 21]; bits[0] = 0; for (int i = 1; i < 1 << 21; ++i) bits[i] = bits[i >> 1] + (i & 1); } ~clique() { delete bits; } // search routine bool search(int step, int size, long long more, long long con); // solve maximum clique and return size int sizeClique(vector<vector<int> >& mat); // solve maximum clique and return constitution vector<int> consClique(vector<vector<int> >& mat); }; // search routine // step is node id, size is current solution, more is available mask, cons is constitution mask bool clique::search(int step, int size, long long more, long long cons) { if (step >= n) { // a new solution reached this->size = size; this->cons = cons; return true; } long long now = ONE << step; if ((now & more) > 0) { long long next = more & mask[step]; if (size + bits[next & MASK] + bits[(next >> 21) & MASK] + bits[next >> 42] >= this->size && size + cmax[step] > this->size) { // the current node is in the clique if (search(step + 1, size + 1, next, cons | now)) return true; } } long long next = more & ~now; if (size + bits[next & MASK] + bits[(next >> 21) & MASK] + bits[next >> 42] > this->size) { // the current node is not in the clique 77 if (search(step + 1, size, next, cons)) return true; } return false; } // solve maximum clique and return size int clique::sizeClique(vector<vector<int> >& mat) { n = mat.size(); // generate mask vectors for (int i = 0; i < n; ++i) { mask[i] = 0; for (int j = 0; j < n; ++j) if (mat[i][j] > 0) mask[i] |= ONE << j; } size = 0; for (int i = n - 1; i >= 0; --i) { search(i + 1, 1, mask[i], ONE << i); cmax[i] = size; } return size; } // solve maximum clique and return constitution // calls sizeClique and restore cons vector<int> clique::consClique(vector<vector<int> >& mat) { sizeClique(mat); vector<int> ret; for (int i = 0; i < n; ++i) if ((cons & (ONE << i)) > 0) ret.push_back(i); return ret; }