題目大意：給出一個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 閱讀(955)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索