3063367_ac_1358ms_38852k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
using namespace std;

int a[15], v[14], m, n;
int dis[14][14];
int f[14][14][1<<14];
__int64 cnt[14][14][1<<14];

struct node 
{
	int no;
	int id;
	int mark[14];
	int pos[14];
}num[1<<13];

bool cmp(struct node c,struct node b)
{
	if (c.no!=b.no)
		return c.no<b.no;
	else
		return c.id<b.id;
}

void init()
{
	int i, k;

	a[1] = 1;
	for (i = 2; i <= 14; i++)
	{
		a[i] = a[i-1]*2;
	}
	for (k = 1; k < (1<<13); k++)
	{
		num[k].id = k;
		num[k].no = 0;
		memset(num[k].mark,0,sizeof(num[k].mark));
		for (i = 1; k >= a[i]; i++)
		{
			if (k&a[i])
			{
				num[k].pos[num[k].no++] = i;
				num[k].mark[i] = 1;
			}
		}	
	}
	sort(&num[1],&num[1]+(1<<13)-1,cmp);
}

int main()
{
	int i, j, lj, t;
	int mark, k, p;
	int c, max, sum;
	int st, ed;
	__int64 tmp;

	init();
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d",&n,&m);
		memset(cnt,0,sizeof(cnt));
		sum = 0;
		memset(f,0,sizeof(f));
		for(i = 1; i <= n; i++)
		{
			scanf("%d",&v[i]);
			sum += v[i];
		}
		mark = 1;
		if(n==1)
		{
			printf("%d 1\n",sum);
			continue;
		}
		memset(dis,0,sizeof(dis));
		for (i = 0; i < m; i++)
		{
			scanf("%d%d",&st,&ed);
			if(st!=ed)
			{
				dis[st][ed] = dis[ed][st] = v[ed]*v[st];
			}
		}
		for (i = 1; mark; i++)
		{
			if (num[i].no==n&&num[i].id==(1<<n)-1)
				mark = 0;
			if (num[i].id>=(1<<n))
			{
				continue;
			}
			if(num[i].no==1)
			{
				continue;
			}
			for (j = 1; j <= n; j++)
			{
				if (num[i].mark[j]==0)
					continue;
				for (lj = 1; lj <= n; lj++)
				{
					if(num[i].mark[lj]==0||dis[j][lj]==0)
						continue;
					if(num[i].no==2)
					{
						cnt[j][lj][num[i].id] = 1;
						f[j][lj][num[i].id] = dis[j][lj];
					}
					else
					{
						p = 0;
						for (k = 0; k < num[i].no; k++)
						{
							if (num[i].pos[k]!=j)
							{
								p |= a[num[i].pos[k]];
							}
						}
						max = 0;
						for (k = 0; k < num[i].no; k++)
						{
							if(num[i].pos[k]!=j&&num[i].pos[k]!=lj&&dis[num[i].pos[k]][lj]&&f[lj][num[i].pos[k]][p])
							{
								c = 0;
								if(dis[num[i].pos[k]][j])
								{
									c = v[num[i].pos[k]]*v[j]*v[lj];
								}
								if(max<dis[j][lj]+f[lj][num[i].pos[k]][p]+c)
								{
									tmp = cnt[lj][num[i].pos[k]][p];
									max = dis[j][lj]+f[lj][num[i].pos[k]][p]+c;
								}
								else
								{
									if(max==dis[j][lj]+f[lj][num[i].pos[k]][p]+c)
									{
										tmp += cnt[lj][num[i].pos[k]][p];
									}
								}
							}
						}
						f[j][lj][num[i].id] = max;
						cnt[j][lj][num[i].id] = tmp;
					}
				}
			}
		}
		__int64 ans;
		max = -1;
		for (i = 1; i <= n; i++)
		{
			for(j = 1; j <= n; j++)
			{
				if (max<f[i][j][(1<<n)-1])
				{
					max = f[i][j][(1<<n)-1];
					ans = cnt[i][j][(1<<n)-1];
				}
				else
				{
					if(max==f[i][j][(1<<n)-1])
					{
						ans += cnt[i][j][(1<<n)-1];
					}
				}
			}
		}
		if(max==0)
		{
			puts("0 0");
			continue;
		}
		printf("%d ",max+sum);
		if(n<3)
			puts("1");
		else
		{
			if(ans%2==1)
				while(1)
					puts("I Love Sql");
			printf("%I64d\n",ans/2);
		}
	}
	return 0;
}