记录编号	28766	评测结果	AAWWWAWAEW
题目名称	600.配药惊魂	最终得分	40
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	0.033 s
提交时间	2011-10-17 13:39:50	内存使用	1.06 MiB

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

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

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

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

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

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)
		{
			swap1(drupow[ll],drupow[rr]);
			swap2(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;
	if (maxm>2)
		return;
	drupow[++num]=power;
	maxdrum[num]=maxm;
	for (i=last+1;i<=drunum;i++)
		if (!poied[last][i])
			makelist(maxm+1,power+drupow[i],i);
}

int main(void)
{
	freopen("drug.in","r",stdin);
	freopen("drug.out","w",stdout);
	int i;
	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]));
	qqsort(drunum+1,num);
	i=drunum+1;
	while (room>0)
	{
		total+=drupow[i]*mininteger(maxdrum[i],room);
		room-=maxdrum[i++];
	}
	printf("%.1lf\n",total);
	fclose(stdin);
	fclose(stdout);
	return(0);
}