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;
}

评论