Pagini recente » Cod sursa (job #349997) | Cod sursa (job #2537548) | Cod sursa (job #1619966) | Cod sursa (job #1498515) | Cod sursa (job #872713)
Cod sursa(job #872713)
#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;
}