首页 > 代码库 > POJ1419 Graph Coloring（最大独立集）（最大团）
POJ1419 Graph Coloring（最大独立集）（最大团）
Graph Coloring
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 4926 | Accepted: 2289 | Special Judge | ||
Description
You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.
Figure 1: An optimal graph with three black nodes
Figure 1: An optimal graph with three black nodes
Input
The graph is given as a set of nodes denoted by numbers 1...n, n <= 100, and a set of undirected edges denoted by pairs of node numbers (n1, n2), n1 != n2. The input file contains m graphs. The number m is given on the first line. The first line of each graph contains n and k, the number of nodes and the number of edges, respectively. The following k lines contain the edges given by a pair of node numbers, which are separated by a space.
Output
The output should consists of 2m lines, two lines for each graph found in the input file. The first line of should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the list of black nodes, separated by a blank.
Sample Input
16 81 21 32 42 53 43 64 65 6
Sample Output
31 4 5
【分析】此题就是求最大独立集。二部图的最大独立集==顶点数-匹配数，普通图的最大独立集==补图的最大团，且此题需要输出路径，所以用最大团的模板算法较好。
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <string>#include <map>#include <queue>#include <vector>#define inf 0x7fffffff#define met(a,b) memset(a,b,sizeof a)typedef long long ll;using namespace std;const int N = 105;const int M = 25005;bool w[N][N];bool use[N]; //进入团的标号bool bestx[N];int cn,bestn,p,e;void dfs(int x) { bool flag; if(x>p) { bestn=cn; //cn的值是递增的 for( int i=1;i<=p; i++) //赋值给另外一个数组， bestx[i]=use[i]; return ; } flag=true; for( int i=1; i<x; i++) if(use[i]&&!w[i][x]) { flag=false; break; } if(flag) { cn++; use[x]=true; dfs(x+1); cn--; use[x]=false;//回溯 } if(cn+p-x>bestn) { //剪枝 dfs(x+1); }}int main() { int num,u,v; scanf("%d",&num); while(num--) { memset(w,true,sizeof(w)); memset(use,false,sizeof(use)); memset(bestx,false,sizeof(bestx)); scanf("%d%d",&p,&e); for(int i=0; i<e; i++) { scanf("%d%d",&u,&v); w[u][v]=false; w[v][u]=false; } cn=bestn=0; dfs(1); printf("%d\n",bestn); for (int i=1; i<=p; i++)if(bestx[i])printf("%d ",i);printf("\n"); } return 0;}
POJ1419 Graph Coloring（最大独立集）（最大团）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。