题意：给定一个邻接矩阵，求最大团。
解法：直接AC。
代码如下：
#include#include #include #include #include using namespace std;int N, mp[55][55];int ret, st[55], cnt[55];void dfs(int x, int num) { int flag; for (int i = x+1; i < N; ++i) { if (!mp[x][i]) continue; if (cnt[i]+num <= ret) return; flag = true; for (int j = 0; j < num; ++j) { if (!mp[i][st[j]]) { flag = false; break; } } if (flag) { st[num] = i; dfs(i, num+1); } } if (num > ret) { ret = num; }}int query() { ret = 0; for (int i = N-1; i >= 0; --i) { st[0] = i; dfs(i, 1); cnt[i] = ret; } return ret;}int main() { while (scanf("%d", &N), N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { scanf("%d", &mp[i][j]); } } printf("%d\n", query()); } return 0; }
老版本：8000MS+，前面的1000MS+
#include#include #include #include #include using namespace std;int N, mp[55][55];int ret, st[55], cnt;void dfs(int x) { if (x >= N) { ret = cnt; return; } int flag = true; for (int i = 0; i < N; ++i) { if (st[i] && !mp[x][i]) { flag = false; break; } } if (flag) { st[x] = 1, ++cnt; dfs(x+1); st[x] = 0, --cnt; } if (cnt+N-1-x > ret) { dfs(x+1); }}int query() { ret = cnt = 0; memset(st, 0, sizeof (st)); dfs(0); return ret;}int main() { while (scanf("%d", &N), N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { scanf("%d", &mp[i][j]); } } printf("%d\n", query()); } return 0; }