/*
推荐题型:五星
题意:对图中节点进行染色,只有黑白可选,要求相邻节点不同色,问黑色最多可有多少个
思路:深度搜索、记忆数组
*/
#include <cstdio>
#include <cstring>
const int nMax=107;
int G[nMax][nMax];
int ans[nMax],res,n;
//answer,result
void dfs(int cur,int *A)
{
int color[nMax];
if(cur==n)
{
int num=0;
for(int i=1;i<=n;i++)
if(A[i])
num++;
if(num>res)
{
res=num;
memcpy(ans,A,sizeof(ans));
//不可对数组参数求字节长,WA原因:memcpy(ans,A,sizeof(ans));
}
return;
}
for(int i=1;i<=n;i++)
if(A[i]<0)
{
memcpy(color,A,sizeof(color));
color[i]=1;
int u=1;
for(int j=1;j<=n;j++)
if(G[i][j] && color[j]<0)
{
color[j]=0;
u++;
}
dfs(cur+u,color);
}
}
int main()
{
//freopen("data.in","r",stdin);
int A[nMax];
int m,k;
scanf("%d",&m);
while(m--)
{
scanf("%d %d",&n,&k);
memset(G,0,sizeof(G));
for(int i=0;i<k;i++)
{
int a,b;
scanf("%d %d",&a,&b);
G[a][b]=G[b][a]=1;
}
res=0;
memset(A,-1,sizeof(A));
dfs(0,A);
printf("%d\n",res);
int first=true;
for(int i=1;i<=n;i++)
if(ans[i])
{
if(!first)
printf(" ");
else
first=false;
printf("%d",i);
}
printf("\n");
}
return 0;
}
/*
该解法思路:二叉树式深度搜索,最优化剪枝
*/
#include <cstdio>
#include <cstring>
const int nMax=107;
int G[nMax][nMax],A[nMax];
int ans[nMax],res,n;
bool check(int dep)
{
for(int i=1;i<=n;i++)
if(G[dep][i] && A[i]==1)
return false;
return true;
}
void dfs(int dep,int now)
{
if(dep>n)
{
if(now>res)
{
res=now;
memcpy(ans,A,sizeof(A));
}
return;
}
if(now+n-dep+1<=res) return;//剪枝
if(check(dep))
{
A[dep]=1;
dfs(dep+1,now+1);
A[dep]=-1;//回溯
}
A[dep]=0;
dfs(dep+1,now);
A[dep]=-1;
}
int main()
{
//freopen("data.in","r",stdin);
int t,k;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
memset(G,0,sizeof(G));
for(int i=0;i<k;i++)
{
int a,b;
scanf("%d %d",&a,&b);
G[a][b]=G[b][a]=1;
}
memset(A,-1,sizeof(A));
res=0;
dfs(1,0);
printf("%d\n",res);
bool first=true;
for(int i=1;i<=n;i++)
if(ans[i])
{
if(!first)
printf(" ");
else
first=false;
printf("%d",i);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
relation-graph图谱移动端适配拖动修复代码
S7-Graph汉化,测试过,好用。复制替换到s7graph文件中即可。
jmeter-graph.jar
neo4j-graph-data-science-1.7.2.jar
A web component to represent a graph data structure in a 3-dimensional space using a force-directed iterative layout. Uses ThreeJS/WebGL for 3D rendering and either d3-force-3d or ngraph for the ...
精英战舰emwin-GRAPH简易示波器代码.rar
本文档主要用于讨论与 S7-GRAPH 编程相关的以下问题: 编程软件的基本信息;基本概念讲解;基本使用讲解;用于示例工程的简单应用例子; 实际使用中常见问题及讲解.
3D-3d-force-graph-vr.zip,虚拟现实中的三维力定向图形组件,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用程序。
maven-graph-plugin-1.16-sources.jar
基于子图的推荐系统,融合异构信息网络Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks
Neo4j,用户手册,涵盖所有集成的图算法及应用场景,非常适合图算法的学习和应用
S7-GRAPH 编程 Programming with S7-GRAPH
S7-Graph汉化补丁给有需要的人 这个只是个补丁,不是程序,汉化的 给积分少人 S7-Graph汉化补丁给有需要的人 这个只是个补丁,不是程序,汉化的 给积分少人S7-Graph汉化补丁给有需要的人 这个只是个补丁,不是...
spark-graphx_2.11-2.4.0-cdh6.1.1.jar
ng-dependency-graph, AngularJS的Chrome 依赖浏览器 AngularJS依赖关系图 AngularJS依赖关系图浏览器。实现为一个 Chrome 扩展插件。 安装扩展后,你可以在 Chrome inspector面板中访问图形。...
Siemens S7-GRAPH V5.3 SP5_21rar,Siemens S7-GRAPH V5.3 SP5_21
3D-3d-force-graph.zip,使用3rejs/webgl的三维力定向图形组件,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用程序。
grunt-angular-architecture-graph, 在. dot 格式中,生成模块依赖关系图 使用angular-architecture-graph创建 Angular 项目的图表。正在启动这个插件需要 Grunt ~0.4.5If之前,请务必先查看一下如何创建 Gruntfile...
automatic-graph-layout, 图形布局和查看的工具集 Microsoft自动图形布局MSAGL 是一个用于图形布局和查看的.NET 库和工具。MSAGL是由微软 Nachmanson 。Sergey Pupyrev 。Tim Dwyer 。Ted Hart和 Roman Prutkin开
Siemens S7-GRAPH V5.3 SP5_22rar,Siemens S7-GRAPH V5.3 SP5_22