记录编号	28778	评测结果	AAAAAAAAAA
题目名称	配药惊魂	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-10-17 14:00:02	内存使用	1.06 MiB

#include <cstdio>
#include <cmath>
using namespace std;

int num,room,drunum,poinum,inbag[20],maxdrum[70000]/*drupow[70000],*/;
double drupow[70000];
bool poied[20][20]={{false}};

void swapreal(double &a,double &b)
{
	double temp;
	temp=a;
	a=b;
	b=temp;
}

void swapinteger(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

int mininteger(int a,int b)
{
	if (a<b)
		return(a);
	else
		return(b);
}

void qqsort(int l,int r)
{
	int ll,rr;
	double temp;
	ll=l;
	rr=r;
	temp=drupow[(l+r)/2];
	while (ll<=rr)
	{
		while (drupow[ll]>temp)
			ll++;
		while (drupow[rr]<temp)
			rr--;
		if (ll<=rr)
		{
			swapreal(drupow[ll],drupow[rr]);
			swapinteger(maxdrum[ll],maxdrum[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

void makelist(int maxm,double power,int last)
{
	int i,j;
	bool able;
	inbag[maxm]=last;
	drupow[++num]=power;
	maxdrum[num]=maxm;
	for (i=last+1;i<=drunum;i++)
	{
		able=true;
		for (j=1;j<=maxm;j++)
			if (poied[i][inbag[j]])
			{
				able=false;
				break;
			}
		if (able)
			makelist(maxm+1,power+drupow[i],i);
	}
}

int main(void)
{
	freopen("drug.in","r",stdin);
	freopen("drug.out","w",stdout);
	int i,temp,temp2;
	double total=0;
	scanf("%d %d %d",&room,&drunum,&poinum);
	for (i=1;i<=drunum;i++)
		scanf("%lf",&drupow[i]);
	for (i=1;i<=poinum;i++)
	{
		scanf("%d %d",&temp,&temp2);
		poied[temp][temp2]=true;
		poied[temp2][temp]=true;
	}
	num=drunum;
	for (i=1;i<=drunum;i++)
		makelist(1,drupow[i],i);
	for (i=drunum+1;i<=num;i++)
		drupow[i]=drupow[i]/maxdrum[i]*sqrt(double(maxdrum[i]));
	if (drunum+1<num)
		qqsort(drunum+1,num);
	i=drunum+1;
	while (room>0&&i<=num)
	{
		total+=drupow[i]*mininteger(maxdrum[i],room);
		room-=maxdrum[i++];
	}
	printf("%.1lf\n",total);
	fclose(stdin);
	fclose(stdout);
	return(0);
}