记录编号	273611	评测结果	AAAAAAAA
题目名称	王伯买鱼	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.436 s
提交时间	2016-06-22 22:35:30	内存使用	0.47 MiB

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *x,const void *y)
{
	return *(int*)y-*(int*)x; 
}
bool t[1005][1005]={0};
int a[1005][2]={0},w[50]={0},v[50]={0},s[50]={0},max=0,k=0,m,n;
void dfs(int deep,int p,int c)
{
	int i,j;
	bool flag;
	if(deep>w[0]||(deep==w[0]&&k<=c))
	{
		flag=0;
		if(k==c)
		  for(i=1;i<=deep;i++)
		    if(s[i]>w[i])
		      break;
		    else if(s[v[i]]<w[v[i]])
		      {flag=1;break;}
		if(flag==0)
		{
		  k=c;
		  w[0]=deep;
		  for(i=1;i<=deep;i++)
		    w[i]=s[i];
		}
	}
	for(i=p+1;i<=n;i++)
	{
	  flag=0;
	  for(j=1;j<=deep;j++)
	    if(t[a[i][1]][s[j]])
	    {
		  flag=1;
	      break;
		}
	  if(!flag&&c+a[i][0]<=m)
	  {
	    s[deep+1]=a[i][1];
	    dfs(deep+1,i,c+a[i][0]);
	  }
	}
}
int cas()
{
	freopen("fish.in","r",stdin); 
	freopen("fish.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++)
	{
	  scanf("%d%d",&a[i][1],&a[i][0]);
	  v[i]=a[i][1];
	}
	qsort(a+1,n,sizeof(a[0]),cmp);//保证最大的放前面
	while(1)
	{
		scanf("%d%d",&x,&y);
		if(!(x||y))
		  break;
		t[x][y]=t[y][x]=1;
	}
	dfs(0,0,0);
	printf("%d %d\n",w[0],k);
	qsort(w+1,w[0],sizeof(w[0]),cmp);
	for(i=w[0];i>=1;i--)
	  printf("%d\n",w[i]);
}
int aaa=cas();
int main(){;}