首页 > 代码库 > 【USACO 2.1】Healthy Holsteins

【USACO 2.1】Healthy Holsteins

/*TASK: holsteinLANG: C++URL: http://train.usaco.org/usacoprob2?a=SgkbOSkonr2&S=holsteinSOLVE: con[i][j]为食物i含有维生素j的量,ned[i]为需要的维生素i的量bfs,用二进制保存状态 */#include<cstdio>#define N 30int v,g,ned[N],con[N][N];int now[N];int l,r,q[40000];bool vis[40000];bool ck(int s){	//check whether state s is satisfied	for(int i=1;i<=v;i++){		int tol=0;		for(int j=0;j<g;j++)			if((1<<j)&s)				tol+=con[j][i];		if(tol<ned[i])return 0;	}	return 1;}void bfs(){	while(l<=r){		int k=q[l++];		if(ck(k)){			int num=0;			for(int i=0;i<g;i++)				if((1<<i)&k)					num++;			printf("%d",num);			for(int i=0;i<g;i++)				if((1<<i)&k)					printf(" %d",i+1);			puts("");			return;		}		for(int i=0;i<g;i++)			if(!vis[k|(1<<i)]){				q[++r]=k|(1<<i);				vis[k|(1<<i)]=1;			}	}}int main(){	freopen("holstein.in","r",stdin);	freopen("holstein.out","w",stdout);	scanf("%d",&v);	for(int i=1;i<=v;i++)		scanf("%d",&ned[i]);	scanf("%d",&g);	for(int i=0;i<g;i++)		for(int j=1;j<=v;j++)			scanf("%d",&con[i][j]);	bfs();}

  

【USACO 2.1】Healthy Holsteins