題目大意：給出一個(gè)Graph，要給這個(gè)Graph上面的vertex涂色，顏色只有兩種：黒和白。相鄰的兩個(gè)vertex不能全涂成黑色。要求黑色的最多。
不要被此題n=100的數(shù)據(jù)規(guī)模嚇倒，100的規(guī)模也是可以搜索的，數(shù)據(jù)也似乎不是很強(qiáng)。我的做法是依次枚舉每個(gè)頂點(diǎn)的狀態(tài)，即是黑色還是白色，這里有兩個(gè)優(yōu)化：1、顯而易見的，如果結(jié)點(diǎn)i有鄰接結(jié)點(diǎn)已經(jīng)是黑色了，那么i只能是白色；2、最優(yōu)性剪枝：如果當(dāng)前搜索到dep層，其中now個(gè)結(jié)點(diǎn)被涂色，已經(jīng)搜索出的最優(yōu)解為ans，如果now+v-dep+1<=ans，就不需要再繼續(xù)搜索下去了，此時(shí)是假設(shè)以后的(v-dep+1)個(gè)結(jié)點(diǎn)全部涂成黑色，即理想狀況。
以下是我的代碼：
#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 閱讀(950)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索