最大团 题目:http://acm.hdu.edu.cn/showproblem.php?pid=1530

Maximum Clique

Problem Description Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex. Input Input contains multiple tests. For each test: The first line has one integer n, the number of vertex. (1 < n <= 50) The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number). A test with n = 0 signals the end of input. This test should not be processed. Output One number for each test, the number of vertex in maximum clique. Sample Input 5 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 Sample Output 4 代码:http://paste.ubuntu.com/7457071/
  1. /*
  2.  * Author: Haipz
  3.  * School: HDU
  4.  * File Name: 1530.cpp
  5.  */
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <ctime>
  9. #include <cctype>
  10. #include <cfloat>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <climits>
  14. #include <iostream>
  15. #include <vector>
  16. #include <string>
  17. #include <stack>
  18. #include <queue>
  19. #include <set>
  20. #include <map>
  21. #include <algorithm>
  22. using namespace std;
  23. const int N = 50;
  24. int g[N + 5][N + 5], alt[N + 5][N + 5], best[N + 5];
  25. bool dfs(int cur, int dep, int &ans) {
  26.     if (cur == 0) {
  27.         if (dep > ans) {
  28.             ans = dep;
  29.             return true;
  30.         } else return false;
  31.     }
  32.     for (int i = 0; i < cur; ++i) {
  33.         if (cur - i + dep <= ans) return false;
  34.         int u = alt[dep][i];
  35.         if (best[u] + dep <= ans) return false;
  36.         int ncur = 0;
  37.         for (int j = i + 1; j < cur; ++j)
  38.             if (g[u][alt[dep][j]]) alt[dep + 1][ncur++] = alt[dep][j];
  39.         if (dfs(ncur, dep + 1, ans)) return true;
  40.     }
  41.     return false;
  42. }
  43. int MaxClique(int n) {
  44.     int ans = 0;
  45.     memset(best, 0, sizeof(best));
  46.     for (int i = n; i >= 1; --i) {
  47.         int cur = 0;
  48.         for (int j = i + 1; j <= n; ++j)
  49.             if (g[i][j]) alt[1][cur++] = j;
  50.         dfs(cur, 1, ans);
  51.         best[i] = ans;
  52.     }
  53.     return ans;
  54. }
  55. int main() {
  56.     int n;
  57.     while (scanf("%d", &n), n) {
  58.         for (int i = 1; i <= n; ++i)
  59.             for (int j = 1; j <= n; ++j) scanf("%d", &g[i][j]);
  60.         printf("%d\n", MaxClique(n));
  61.     }
  62.     return 0;
  63. }
转载保留版权:http://haipz.com/blog/i/2611 - 海胖博客