`
digiter
  • 浏览: 120719 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

maximum clique 最大团

    博客分类:
  • ICPC
J# 
阅读更多
最大团模板
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define out(v) cout << #v << ": " << (v) << endl
#define MP(X,Y) make_pair(X,Y)
using namespace std;
typedef long long LL;

// maximum clique
// tested: hdu3585, zju1492, pku1129
// paper: A Fast Algorithm For The Maximum Clique Problem
const int MAXN = 27;
int n;
bool G[MAXN][MAXN]; // indexed from one, adjacency matrix
int list[MAXN][MAXN], degree[MAXN], behide[MAXN];
int found, curmax;

void sortdegree() {
	for (int i = 1; i <= n; i++) {
		int k = i;
		for (int j = i + 1; j <= n; j++)
			if (degree[j] < degree[k]) k = j;
		if (k != i) {
			swap(degree[i], degree[k]);
			for (int t = 1; t <= n; t++) swap(G[i][t], G[k][t]);
			for (int t = 1; t <= n; t++) swap(G[t][i], G[t][k]);
		}
	}
}
void dfs(int d){
	if (d - 1 > curmax) { found = 1; return; };
	int i, j;
	for (int i = 1; i < list[d - 1][0] - curmax + d; i++)
		if (!found && d + behide[list[d - 1][i] + 1] > curmax
		 &&	(list[d - 1][0] == i || d + behide[list[d - 1][i + 1]] > curmax)) {
			for (j = i + 1, list[d][0] = 0; j <= list[d - 1][0]; j++)
				if (G[list[d - 1][j]][list[d - 1][i]])
					list[d][++list[d][0]] = list[d - 1][j];
				if (list[d][0] == 0 || d + behide[list[d][1]] > curmax)
					dfs(d + 1);
		}
}
int solve() {
	for (int i = 1; i <= n; i++) {
		degree[i] = 0;
		for (int j = 1; j <= n; j++) degree[i] += G[i][j];
	}
	sortdegree(); behide[n + 1] = 0; behide[n] = 1;
	for (int i = n - 1; i > 0; i--) {
		curmax = behide[i + 1]; found = list[1][0] = 0;
		for (int j = i + 1; j <= n; j++)
			if (G[j][i]) list[1][++list[1][0]] = j;
		dfs(2); behide[i] = curmax + found;
	}
	return behide[1];
}

int set[MAXN];
int main()
{
	char line[30];
	while (scanf("%d", &n), n != 0)
	{
		memset(G, false, sizeof(G));
		for (int i = 1; i <= n; ++i)
		{
			scanf("%s", line);
			int u = line[0] - 'A' + 1;
			set[i] = u;
			for (int j = 2; line[j]; ++j)
				G[u][line[j] - 'A' + 1] = true;
		}
		int cnt = solve();
		printf("%d channel%s needed.\n", cnt, cnt == 1 ? "" : "s");
		for (int i = 1; i <= list[1][0]; ++i)
			cout << char('A' + list[1][i] - 1) << " ";
		cout << endl;
	}

	return 0;
}
分享到:
评论

相关推荐

    MCP.rar_clique_maximum clique_最大团_最大团问题

    最大团问题是图论中的一个经典问题,主要研究的是在一个无向图中找到具有最多顶点的完全子图,其中每两个顶点之间都存在边。这个完全子图就被称为最大团。在社会网络、计算机科学、化学等领域都有广泛应用,比如在...

    最大团快速算法

    在计算机科学与图论领域,最大团问题(Maximum Clique Problem)是一项经典而重要的课题。它涉及到在一个无向图中寻找最大的完全子图(即团),其中任意两个顶点之间都有边相连。这一问题不仅在理论研究上具有挑战性...

    matlab 求最大团

    在计算机科学领域,最大团问题(Maximum Clique Problem, MCP)是一个经典的图论问题,它涉及到寻找一个无向图中最大的完全子图,即每个节点都与其他所有节点相连的子图。在MATLAB环境中解决这个问题可以采用不同的...

    最大团分支限界法PPT

    最大团分支限界法PPT 最大团问题是图论中一个著名的问题,目标是找到给定图中的最大完全子图。最大团问题可以使用分支限界法来解决,本文将详细介绍最大团问题的定义、问题分析、算法设计和算法实现。 1. 问题描述...

    无向图中最大团问题的matlab代码

    MCP函数(Maximum Clique Problem)是这个代码的核心部分,它接受一个无向图的邻接矩阵作为输入,通过递归回溯过程寻找可能的最大团。在回溯过程中,MCP函数会维护当前的团,以及所有可能的下一步选择。当找到一个更...

    论文研究-最大团问题研究进展及算法测试标准.pdf

    最大团问题(Maximum Clique Problem, MCP)是图论和组合优化领域中的一个经典问题,广泛应用于各种实际问题中,如社交网络分析、生物信息学、工业生产调度等。最大团问题是寻找一个图中最大的完全子图,即顶点之间...

    最大团问题研究进展及算法测试标准.pdf

    最大团问题(Maximum Clique Problem, MCP)是图论中的一个重要且经典的组合优化问题,属于NP完全问题。该问题不仅在理论上有着重要的意义,在实际应用中也有着广泛的用途,如市场分析、方案选择、信号传输、计算机...

    最大团 EWLS 论文

    这个问题的重要性在于其在理论和应用上的广泛性,比如它可以转化为最大独立集(Maximum Independent Set,简称MIS)问题和最大团(Maximum Clique,简称MC)问题。此外,最小顶点覆盖问题是NP难问题,这意味着在...

    maximum-clique:最大点击子图

    最大集团 在计算机科学中,团问题是指与在图中查找特定完整子图(“团”)相关的任何问题,即每对元素连接的元素集。 例如,最大集团问题出现在以下现实世界中。 考虑一个社交网络,其中图的顶点代表人,图的边代表...

    启发式算法求解最大团问题研究.pdf

    最大团问题(Maximum Clique Problem, MCP)作为图论中的一个经典组合优化问题,在理论研究和实际应用方面都具有重要意义。该问题属于NP完全问题,即它是难以在多项式时间内找到最优解的问题之一。尽管如此,由于其在...

    关于最大团问题的一种新算法

    最大团问题(Maximum Clique Problem, MCP)是图论中的一个重要问题,在计算机科学、社会网络分析、生物信息学等领域有着广泛的应用。MCP的目标是在给定的无向图\( G=(V,E) \)中找到一个最大的完全子图(即团)。这里...

    蔡少伟最大团方法1

    蔡少伟最大团方法1是一种求解图论问题的算法,特别关注于寻找图的最大顶点覆盖(Maximum Vertex Cover, MVC)或最大团(Maximum Clique)。最大顶点覆盖问题是指在无向图中找到一个尽可能大的顶点子集,使得这个子...

    最大团问题研究进展及算法测试标准* (2007年)

    最大团问题(Maximum Clique Problem,MCP)是图论中的一个重要问题,它在理论计算机科学领域具有非常重要的地位。最大团问题研究的内容是,在一个无向图中寻找最大的完全子图(即图中的一个团),其中任意两个不同...

    一种最大团问题的Tile自组装高效模型

    最大团问题(Maximum Clique Problem, MCP)是组合数学和图论中的一个重要问题,属于NP-hard问题,即在多项式时间内很难找到一个图的最大团。一个图的“团”是指一个顶点的子集,其中任意两个顶点都相互连接。而...

    弦图与区间图(修正版)

    - **最大团(Maximum Clique):** 所有团中顶点数最多的一个团被称为最大团。找到一个图的最大团是一个NP完全问题,但在特定类型的图中,如弦图,这个问题变得更为简单。 #### 图着色 - **最小染色(Minimum Coloring...

    ACMC语言浙大模板

    ACMC语言浙大模板 ACMC语言浙大模板是一种功能强大且实用的算法模板,包含了多种经典算法和...8. 最大团(Maximum Clique):最大团是一种图论问题,旨在找到图中的最大团。它可以用于解决资源分配和任务调度问题。

    大型图的最大重量团的有效本地搜索

    1. 最大权重团问题(Maximum Weight Clique,MWC):这是一个定义在加权图上的问题,其中每个顶点和每条边都有一个权重。目标是找到一个顶点子集,使得子集内的任意两个顶点都是相互连接的,并且子集的权重总和最大...

Global site tag (gtag.js) - Google Analytics