#include<stdio.h>
#include<string.h>
int s[14][3000],q0[14],q1[14],bian[13][13],q,i,j,k,t1,t2,b,c,iq,tp1,tp2;
__int64 f[8192][13][13],ways[8192][13][13],max,v[13],add,count;
void generate_s(int c)
{
	int i,j,tp;
	for(i=0;i<=13;++i) s[i][0]=0;
	for(i=0;i<1<<c;++i){
		tp=0;
		for(j=0;j<c;++j)
			if((i>>j)&1) ++tp;
		s[tp][++s[tp][0]]=i;
	}
}
void generate_q()
{
	int r;
	q1[0]=0;q0[0]=0;
	for(r=0;r<c;++r)
		if((s[i][j]>>r)&1) q1[++q1[0]]=r;
		else q0[++q0[0]]=r;
}
int main()
{
	scanf("%d",&q);
	for(iq=1;iq<=q;++iq){
		memset(bian,0,sizeof(bian));
		memset(f,0,sizeof(f));
		memset(ways,0,sizeof(ways));
		scanf("%d %d",&c,&b);
		generate_s(c);
		for(i=0;i<c;++i)
			scanf("%d",&v[i]);
		for(i=1;i<=b;++i){
			scanf("%d %d",&tp1,&tp2);
			bian[--tp1][--tp2]=1;
			bian[tp2][tp1]=1;
		}

		for(i=0;i<c;++i)
			for(j=0;j<c;++j)
				if(bian[i][j]){
					f[1<<i|1<<j][i][j]=v[i]+v[j]+v[i]*v[j];
					ways[1<<i|1<<j][i][j]=1;
				}
		for(i=2;i<c;++i)
			for(j=1;j<=s[i][0];++j){
				generate_q();
				for(k=1;k<=q0[0];++k)
					for(t1=1;t1<=q1[0];++t1)
						for(t2=1;t2<=q1[0];++t2)
							if(bian[q1[t1]][q1[t2]] && bian[q1[t2]][q0[k]]){
								add=v[q0[k]]+v[q1[t2]]*v[q0[k]];
								if(bian[q1[t1]][q0[k]]) add+=v[q1[t1]]*v[q1[t2]]*v[q0[k]];
								if(f[s[i][j]|(1<<q0[k])][q1[t2]][q0[k]]<f[s[i][j]][q1[t1]][q1[t2]]+add){
									ways[s[i][j]|(1<<q0[k])][q1[t2]][q0[k]]=ways[s[i][j]][q1[t1]][q1[t2]];
									f[s[i][j]|(1<<q0[k])][q1[t2]][q0[k]]=f[s[i][j]][q1[t1]][q1[t2]]+add;
								}
								else if(f[s[i][j]|(1<<q0[k])][q1[t2]][q0[k]]==f[s[i][j]][q1[t1]][q1[t2]]+add){
									ways[s[i][j]|(1<<q0[k])][q1[t2]][q0[k]]+=ways[s[i][j]][q1[t1]][q1[t2]];
								}
							}
			}

		count=0;max=0;
		for(i=0;i<c;++i)
			for(j=0;j<c;++j)
				if(bian[i][j] && f[(1<<c)-1][i][j]>max) max=f[(1<<c)-1][i][j];
		for(i=0;i<c;++i)
			for(j=0;j<c;++j)
				if(bian[i][j] && f[(1<<c)-1][i][j]==max) count+=ways[(1<<c)-1][i][j];
		if(c==1) printf("%d 1\n",v[0]);
		else printf("%I64d %d\n",max,count/2);
	}
	return 0;
	
}

• Re:谁能帮我看看啊，老是wa...哭了～ (215) boycott 2009-02-09 10:54:57