Islands and Bridges 题解

Islands and Bridges

Description

给定一些岛屿和一些连接岛屿的桥梁，大家都知道汉密尔顿路是访问每个岛屿一次的路线，在我们这个地图中，每个岛屿有个正整数的权值，表示这个岛屿的观赏价值。假设一共有N个岛屿，用Vi表示岛屿Ci的价值，汉密尔顿路C1C2…Cn的价值是以下三部分的总和：
(1)所有岛屿的价值之和；
(2)对于路径中相邻的两个岛屿CiCi+1,把两个岛屿的价值之积加到总价值中；
(3)路径中连续三个岛屿CiCi+1Ci+2，如果Ci与Ci+2有桥直接相连，则把这三个岛屿价值之积加到总价值中。
要求计算汉密尔顿路最大的价值以及方案数。

Input

输入第一行是一个整数Q(Q<=20)，表示测试数据的数量。每个测试数据第一行输入两个整数N和M,分别表示岛屿数和桥梁数，接下来一行包含N个正整数，第i个数表示Vi，每个数不超过100,最后M行，每行两个数X,Y，表示岛X和岛Y之间有一座桥直接相连，桥是双向的，岛屿编号为1到N(N<=13)

Output

对于每个测试数据，输出一行，两个整数，第一个数表示最大价值，第二个数表示方案数，如果不存在汉密尔顿路径，输出“0 0”
注意：一条路径可以反着走，我们认为这两条路径是同一条路径。

Sample Input

2
3 3
2 2 2
1 2
2 3
3 1
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output

22 3
69 1

题解

emmmmmm这题只有一个测试点，不成功便成仁
老套路了，$N\le 13$的数据用ass想都知道是状压， 根据题目统计答案的规则，我们需要记录上一个和上上个走到的点，所以我们设$f[s][i][j]$表示当前走过点的状态为$s$（1表示走过，0表示没走过），上一个走到的是点$i$，上上个走到的是点$j$之后时最大的总价值是多少，于是我们就可以先预处理出经过两个点的状态，然后枚举每一个状态暴力DP转移就行了
至于统计方案数也很简单，设一个$g[s][i][j]$表示在$f[s][i][j]$情况下的方案数，转移时只要判断一下有没有大于原来的$f$，如果大于则$g$就赋值成转移过来的那个状态的$g$，如果等于就加上转移过来那个状态的$g$就行了
之后注意当只有一个岛的时候是可以走完的，需要特判一下

CODE

#include<cstdio>
#include<string>
#include<cstring>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 15
#define ll long long
using namespace std;
int q,n,m,ans1,a[N],f[1<<(N-1)][N][N];
ll g[1<<(N-1)][N][N],ans2;
bool b[N][N]; 
inline void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
int main()
{
	read(q);
	while (q--)
	{
		read(n);read(m);
		for (R i=1;i<=n;++i)
			read(a[i]);
		if (n==1) {printf("%d 1\n",a[1]);continue;}
		memset(b,0,sizeof(b));
		for (R i=1;i<=m;++i)
		{
			int x,y;read(x);read(y);
			b[x][y]=b[y][x]=1;
		}
		memset(f,0,sizeof(f));memset(g,0,sizeof(0));
		for (R i=1;i<=n;++i)
			for (R j=1;j<=n;++j)
				if (i!=j && b[i][j]) f[(1<<i-1)|(1<<j-1)][i][j]=a[i]*a[j]+a[i]+a[j],g[(1<<i-1)|(1<<j-1)][i][j]=1;
		int tot=(1<<n)-1;
		for (R s=0;s<=tot;++s)
			for (R i=1;i<=n;++i)
				if ((s&(1<<i-1)))
					for (R j=1;j<=n;++j)
						if (j!=i && s&(1<<j-1) && b[i][j])
							for (R k=1;k<=n;++k)
								if (k!=i && k!=j && s&(1<<k-1) && b[k][j])
								{
									int now=s-(1<<i-1);
									if (f[now][j][k])
									{
										int num=f[now][j][k]+a[i]*a[j]+a[i];
										if (b[i][k]) num+=a[i]*a[j]*a[k];
										if (num>f[s][i][j]) f[s][i][j]=num,g[s][i][j]=g[now][j][k];
										else if (num==f[s][i][j]) g[s][i][j]+=g[now][j][k];
									}
								}
		ans1=ans2=0;
		for (R i=1;i<=n;++i)
			for (R j=1;j<=n;++j)
				if (i!=j)
				{
					if (f[tot][i][j]>ans1) ans1=f[tot][i][j],ans2=g[tot][i][j];
					else if (f[tot][i][j]==ans1) ans2+=g[tot][i][j];
				}
		printf("%d %lld\n",ans1,ans1>0?ans2>>1:0);
	} 
	return 0;
}