Cod sursa(job #872713)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 6 februarie 2013 15:32:31
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <iomanip>
#include <limits.h>
using namespace std;
ifstream cin("reteta.in");
ofstream cout("reteta.out");
int n, m, i, j, tip, q, x;
double a[30][25], cost[25];
int st[25];
double suma_min=INT_MAX;
void afisare(int p)
{
    int i;
    double suma=0;
//  for(i=1;i<=m;i++)
//    {for(j=1;j<=n; j++)
//       cout<<a[i][j]<<" ";
//    cout<<"\n";}
    for(j=1;j<=p;j++)
        for(i=1;i<=n;i++)
            if(a[st[j]][i])
               { suma=suma+(double)(cost[i]/a[st[j]][i]);
               //  a[st[j]][i]=(double)(cost[i]/a[st[j]][i]);

                }
    suma_min=min(suma, suma_min);
//    cout<<suma<<"\n";
//   for(i=1;i<=m;i++)
//    {for(j=1;j<=n;j++)
//       cout<<a[i][j]<<" ";
//    cout<<"\n";}

//    for(i=1;i<=p;i++)
//       cout<<st[i]<<" ";
//       cout<<"\n";
//
}
int valid(int p)
{
    int i, contor=0, final=0;
    for(i=1;i<=n;i++)
       {
            contor=0;
            for(j=1;j<=p;j++)
                if(a[st[j]][i])
                    contor++;
                if(contor==1)
                    final++;
                    else
                        return 0;
                }
    if(final==n)
        return 1;
    return 0;
}
void back(int p)
{
    int pval;
    for(pval=st[p-1]+1;pval<=m;pval++)
    {

        st[p]=pval;
        if(valid(p))
        afisare(p);
        back(p+1);
    }
}
int main()
{
    ///citire
    cin>>n>>m;
    for(i=1;i<=m;i++)
        {
            cin>>tip>>q;
            for(j=1;j<=q;j++)
                {
                    cin>>x;
                    a[i][x]=tip;
                }
        }
    for(i=1;i<=n;i++)
            cin>>cost[i];
    back(1);
    cout<<fixed<<setprecision(1)<<suma_min<<"\n";
    return 0;
}