浙江财经大学
信息管理与工程学院

最大团问题

本文由 Ocrosoft 于 2016-12-25 10:47:32 发表

在一个无向图中,最大团是不包含在更大的完全子图中的一个完全子图(完全子图:任意两个点之间都有连接)。

#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
*/

欢迎分享与转载,请保留链接与出处。Ocrosoft » 最大团问题

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址