dfs
代码:
#include<algorithm> #include<iostream> #include<cstdio> using namespace std; int n,m,p,q,ans1,ans2,len; int ans[35],sum[35]; bool ok[35]; struct haochi { int zl,jg,ctb; int tot,dr[35]; friend bool operator < (const haochi &x,const haochi &y) { return x.zl<y.zl; } }yu[35]; void dfs(int hao,int lei,int qian) { if(qian>m)return; if(hao==n+1) { if((lei>ans1)||(lei==ans1&&qian>ans2)) { len=0; for(int i=1;i<=n;++i) if(ok[i])ans[++len]=i; ans1=lei; ans2=qian; } return; } if(lei+(n-hao+1)<ans1 || (lei+(n-hao+1) ==ans1 && qian+sum[hao]<=ans2))return; if(yu[hao].ctb) { dfs(hao+1,lei,qian); return; } ok[hao]=1; for(int i=1;i<=yu[hao].tot;++i)yu[yu[hao].dr[i]].ctb++; dfs(hao+1,lei+1,qian+yu[hao].jg); ok[hao]=0; for(int i=1;i<=yu[hao].tot;++i)yu[yu[hao].dr[i]].ctb--; dfs(hao+1,lei,qian); } int main() { freopen("fish.in","r",stdin); freopen("fish.out","w",stdout); cin>>m>>n; for(int i=1;i<=n;++i) scanf("%d%d",&yu[i].zl,&yu[i].jg); sort(yu+1,yu+1+n); for(int i=n;i>=1;i--)sum[i]=sum[i+1]+yu[i].jg; while(scanf("%d%d",&p,&q)&&p&&q) { yu[p].dr[++yu[p].tot]=q; yu[q].dr[++yu[q].tot]=p; } dfs(1,0,0); cout<<ans1<<" "<<ans2<<endl; for(int i=1;i<=len;i++)printf("%d\n",ans[i]); fclose(stdin);fclose(stdout); return 0; } /* 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 0 */