记录编号	332801	评测结果	AAAAAAAA
题目名称	王伯买鱼	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.520 s
提交时间	2016-10-29 10:07:52	内存使用	0.07 MiB

#include<cstdio>
#include<algorithm>
#include<ctime>
#define is(a) ((a)>='0'&&(a)<='9')
using namespace std;
char ch;bool read_flag;
inline void read(int& x)
{
	read_flag=false;
	while(ch=getchar(),!is(ch))if(ch=='-')read_flag=1;
	x=ch^'0';
	while(ch=getchar(),is(ch)) x=x*10+(ch^'0');
	if(read_flag) x=-x;
}
struct Fish{
	int id,cost;
	bool operator < (const Fish& temp)const{
		return cost>temp.cost;
	}
}a[35];
bool ifin[35],ans[35],temp_ans[35];
int n,m,fish_num,fish_cost,been[35][35];
inline bool judge(int x)
{
	for(int i=1;i<=been[x][0];i++)
	  if(ifin[been[x][i]]) return true;
	return false;
}
inline void dfs(int deep,int nowm,int nowc)
{
	if(nowc>n) return ;
	if(fish_num<nowm||(fish_cost<=nowc&&fish_num==nowm)){
		fish_cost=nowc,fish_num=nowm;
		for(int i=1;i<=m;i++) ans[i]=temp_ans[i];
	}
	if(deep>m)return ;
	bool ifen=false;
	if(judge(a[deep].id)) ifen=true;
	if(!ifen)
		temp_ans[a[deep].id]=ifin[a[deep].id]=1,
		dfs(deep+1,nowm+1,nowc+a[deep].cost),
		temp_ans[a[deep].id]=ifin[a[deep].id]=0;
	dfs(deep+1,nowm,nowc);
}
int _521()
{
#define enjoy_coding
#ifdef enjoy_coding
	freopen("fish.in","r",stdin);
	freopen("fish.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int i,j,k;
	read(n),read(m);
	for(i=1;i<=m;i++) read(a[i].id),read(a[i].cost);
	while(read(j),read(k),j&&k) been[j][++been[j][0]]=k,been[k][++been[k][0]]=j;
	sort(a+1,a+m+1);
	dfs(1,0,0);
	printf("%d %d\n",fish_num,fish_cost);
	for(i=1;i<=m;i++) if(ans[i]) printf("%d\n",i);
	//printf("%.3lf\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}
int _520=_521();
int main(){;}