﻿最大团问题-Ocrosoft

# 最大团问题

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
#define pree(a,v,b) for(int a=v;a>=b;a--)
#define lowbit(x) x&-x
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 27 + 10;
const int MOD = 1000000007;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
int mp[100][100];
int n, best_ans = 0;
vector<vector<int> >ans;
vector<int> v;
bool check(int p)
{
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (!mp[p][*it])return false;
it++;
}
return true;
}
void dfs(int p)
{
if (n - p + v.size() < best_ans)return;//剪枝，剩下的(含当前)+数组中的小于当前最佳答案
if (p >= n)
{
for (int i = 0; i < v.size(); i++)
printf("%d ", v[i]);
printf("\n");
//ans.push_back(v);
best_ans = v.size();
return;
}
if (check(p))
{
v.push_back(p);
dfs(p + 1);
v.pop_back();
}
dfs(p + 1);
return;
}
int main()
{
cin >> n;
rep(i, 0, n)rep(j, 0, n)cin >> mp[i][j];
dfs(0);
printf("最大团顶点个数:%d\n", best_ans);
/*
for (int i = 0; i < v.size(); i++)
{
if (ans[i].size() == best_ans)
{
for (int j = 0; j < ans[i].size(); j++)
printf("%d ", ans[i][j]);
printf("\n");
}
}
*/
return 0;
}
/*
5
0 1 0 1 1
1 0 1 0 1
0 1 0 0 1
1 0 0 0 1
1 1 1 1 0
*/```