题目大意：给出一个Graph，要给这个Graph上面的vertex涂色，颜色只有两种：黒和白。相邻的两个vertex不能全涂成黑色。要求黑色的最多。
不要被此题n=100的数据规模吓倒，100的规模也是可以搜索的，数据也似乎不是很强。我的做法是依次枚举每个顶点的状态，即是黑色还是白色，这里有两个优化：1、显而易见的，如果结点i有邻接结点已经是黑色了，那么i只能是白色；2、最优性剪枝：如果当前搜索到dep层，其中now个结点被涂色，已经搜索出的最优解为ans，如果now+v-dep+1<=ans，就不需要再继续搜索下去了，此时是假设以后的(v-dep+1)个结点全部涂成黑色，即理想状况。
以下是我的代码：
#include<stdio.h>
const long maxv=102;
long v,e,ans,a[maxv];
bool g[maxv][maxv];
int d[maxv];
bool ok(long node)
{
for(long i=1;i<=v;i++)
if(g[node][i]&&d[i]==1)
return false;
return true;
}
void dfs(long dep,long now)
{
if(dep>v)
{
if(now>ans)
{
ans=now;
for(long i=1;i<=v;i++) a[i]=d[i];
}
return;
}
if(now+v-dep+1<=ans) return;
if(ok(dep))
{
d[dep]=1;
dfs(dep+1,now+1);
d[dep]=0;
}
dfs(dep+1,now);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
long test;
bool first;
scanf("%ld",&test);
while(test--)
{
scanf("%ld%ld",&v,&e);
for(long i=0;i<=v;i++)
for(long j=0;j<=v;j++)
g[i][j]=false;
for(long i=0;i<=v;i++) d[i]=0;
ans=0;
// Clear
for(long i=1;i<=e;i++)
{
long a,b;
scanf("%ld%ld",&a,&b);
g[a][b]=g[b][a]=true;
}
dfs(1,0);
printf("%ld\n",ans);
first=true;
for(long i=1;i<=v;i++)
if(a[i])
{
if(first) first=false;
else putchar(' ');
printf("%ld",i);
}
putchar('\n');
}
return 0;
}
posted on 2010-01-09 22:19
lee1r 阅读(936)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索