DFS，规模很小，直接搜过#include<iostream>using namespace std;int n;double sum,m;bool mark[11],escape;struct vex{    int num,count[11];    double per;}a[12];void dfs(int si,int num,double max){    int total=0,i;    double temp;    if(num==n)    {        if(max>sum)sum=max;        escape=1;        return;    }    if(si==n+1)return;    for( i=1;i<=a[si].num;i++)    {        if(mark[a[si].count[i]]){mark[a[si].count[i]]=0;total++;}        else {mark[a[si].count[i]]=1;total--;}            }    temp=max;    max=max*(1-(a[si].per/100));    dfs(si+1,num+total,max);    total=0;    for(i=1;i<=a[si].num;i++)    {        if(mark[a[si].count[i]])mark[a[si].count[i]]=0;        else mark[a[si].count[i]]=1;    }        dfs(si+1,num,temp);}int main(){    int i,j;    while(cin>>n>>m &&(n))    {        escape=0;        memset(mark,1,sizeof(mark));        for(i=1;i<=n;i++)        {            cin>>a[i].num;            for(j=1;j<=a[i].num;j++)                cin>>a[i].count[j];            a[i].count[j]=i;            a[i].num++;            cin>>a[i].per;        }        sum=0;        dfs(1,0,m);        if(escape)printf("%.2lf\n",sum);        else printf("-1\n");    }    return 0;}

评论