比赛 |
20160708BDFS |
评测结果 |
AAAAAAATAT |
题目名称 |
荷斯坦奶牛 |
最终得分 |
80 |
用户昵称 |
cdcq |
运行时间 |
2.009 s |
代码语言 |
C++ |
内存使用 |
0.29 MiB |
提交时间 |
2016-07-08 09:49:17 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[110][110],b[110];
int k=0;
bool found=false;
int dui[110],tou=0;
bool visited[110];
int c[110];
bool check(){
memset(c,0,sizeof(c));
for(int i=1;i<=tou;i++)
for(int j=1;j<=n;j++)
c[j]+=a[dui[i]][j];
for(int i=1;i<=n;i++)
if(c[i]<b[i])
return false;
return true;
}
void dfs(int x){
if(found)
return ;
if(x==k){
if(check()){
found=true;
cout<<tou<<" ";
for(int i=1;i<=tou;i++)
cout<<dui[i]<<" ";
cout<<endl;
}
return ;
}
for(int i=1;i<=m;i++)
if(!visited[i]){
dui[++tou]=i;
visited[i]=true;
dfs(x+1);
if(found)
return ;
tou--;
visited[i]=false;
}
return ;
}
int main(){
//freopen("ddd.in","r",stdin);
freopen("holstein.in","r",stdin);
freopen("holstein.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
cin>>b[i];
cin>>m;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(k=1;k<=m;k++){
memset(visited,0,sizeof(visited));
tou=0;
dfs(0);
if(found)
return 0;
}
return 0;
}