Islands and Bridges
| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 7821 | Accepted: 2003 |
Description
Given a map of islands and bridges that connect these islands, a Hamilton path, as we all know, is a path along the bridges such that it visits each island exactly once. On our map, there is also a positive integer value associated
with each island. We call a Hamilton path the best triangular Hamilton path if it maximizes the value described below.
with each island. We call a Hamilton path the best triangular Hamilton path if it maximizes the value described below.
Suppose there are n islands. The value of a Hamilton path C1C2...Cn is calculated as the sum of three parts. Let Vi be the value for the island Ci. As the first part, we sum over all the Vi values for each island in the path. For the second part, for each edge
CiCi+1 in the path, we add the product Vi*Vi+1. And for the third part, whenever three consecutive islands CiCi+1Ci+2 in the path forms a triangle in the map, i.e. there is a bridge between Ci and Ci+2,
we add the product Vi*Vi+1*Vi+2.
Most likely but not necessarily, the best triangular Hamilton path you are going to find contains many triangles. It is quite possible that there might be more than one best triangular Hamilton paths; your second task is to find the number of such paths.
Input
The input file starts with a number q (q<=20) on the first line, which is the number of test cases. Each test case starts with a line with two integers n and m, which are the number of islands and the number of bridges in the map,
respectively. The next line contains n positive integers, the i-th number being the Vi value of island i. Each value is no more than 100. The following m lines are in the form x y, which indicates there is a (two way) bridge between island x and island y.
Islands are numbered from 1 to n. You may assume there will be no more than 13 islands.
respectively. The next line contains n positive integers, the i-th number being the Vi value of island i. Each value is no more than 100. The following m lines are in the form x y, which indicates there is a (two way) bridge between island x and island y.
Islands are numbered from 1 to n. You may assume there will be no more than 13 islands.
Output
For each test case, output a line with two numbers, separated by a space. The first number is the maximum value of a best triangular Hamilton path; the second number should be the number of different best triangular Hamilton paths.
If the test case does not contain a Hamilton path, the output must be `0 0'.
If the test case does not contain a Hamilton path, the output must be `0 0'.
Note: A path may be written down in the reversed order. We still think it is the same path.
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
Source
题目描述：
给定一个地图，地图中有许多岛屿，岛屿之间用桥连接。汉密尔顿路径，是一条沿着桥访问
每个岛屿一次且仅一次的路径。在地图中，每个岛屿还有一个正整数权值与之关联。如果某条汉
密尔顿路径使得下面描述的值取得最大，则称这条汉密尔顿路径为最好的三角汉密尔顿路径。
假定有n 个岛屿，令Vi 为岛屿Ci 的权值。一条汉密尔顿路径C1C2...Cn 的值为三部分之和：
第1 部分，将路径中每个岛屿的权值累加起来；第2 部分，对路径中的每条边(Ci Ci+1)，将乘积
Vi * Vi+1 累加起来；第3 部分，当路径中连续的3 个岛屿Ci、Ci+1 和Ci+2 形成一个三角形，即
在岛屿Ci 和Ci+2 之间有一座桥，则把乘积Vi * Vi+1 * Vi+2 累加起来。
最好的三角汉密尔顿路径中可能包含多个三角形。在一幅地图中可能也存在多个最好的三角
汉密尔顿路径，你的第二个任务是计算这些路径的数目。
输入描述：
输入文件的第1 行为一个数q，q≤20，表示测试数据的个数。每个测试数据的第1 行为两个
整数：n 和m，分别表示岛屿的数目和桥的数目，岛屿的编号从1～n，其中n≤13；接下来一行
包含n 个正整数，第i 个正整数表示第i 个岛屿的权值，每个权值都不超过100；接下来有m 行，
每行的格式为：x y，表示有一座双向的桥，连接岛屿x 和岛屿y。
输出描述：
对输入文件中的每个测试数据，输出一行，为两个数，用空格隔开。第1 个数为最好的三角
汉密尔顿路径的权值；第2 个数为不同的最好的三角汉密尔顿的数目。如果地图中不存在汉密尔
顿路径，则输出0 0。
注意：一条路径可以以相反的顺序来表示，但这与原来的路径是同一条路径。
给定一个地图，地图中有许多岛屿，岛屿之间用桥连接。汉密尔顿路径，是一条沿着桥访问
每个岛屿一次且仅一次的路径。在地图中，每个岛屿还有一个正整数权值与之关联。如果某条汉
密尔顿路径使得下面描述的值取得最大，则称这条汉密尔顿路径为最好的三角汉密尔顿路径。
假定有n 个岛屿，令Vi 为岛屿Ci 的权值。一条汉密尔顿路径C1C2...Cn 的值为三部分之和：
第1 部分，将路径中每个岛屿的权值累加起来；第2 部分，对路径中的每条边(Ci Ci+1)，将乘积
Vi * Vi+1 累加起来；第3 部分，当路径中连续的3 个岛屿Ci、Ci+1 和Ci+2 形成一个三角形，即
在岛屿Ci 和Ci+2 之间有一座桥，则把乘积Vi * Vi+1 * Vi+2 累加起来。
最好的三角汉密尔顿路径中可能包含多个三角形。在一幅地图中可能也存在多个最好的三角
汉密尔顿路径，你的第二个任务是计算这些路径的数目。
输入描述：
输入文件的第1 行为一个数q，q≤20，表示测试数据的个数。每个测试数据的第1 行为两个
整数：n 和m，分别表示岛屿的数目和桥的数目，岛屿的编号从1～n，其中n≤13；接下来一行
包含n 个正整数，第i 个正整数表示第i 个岛屿的权值，每个权值都不超过100；接下来有m 行，
每行的格式为：x y，表示有一座双向的桥，连接岛屿x 和岛屿y。
输出描述：
对输入文件中的每个测试数据，输出一行，为两个数，用空格隔开。第1 个数为最好的三角
汉密尔顿路径的权值；第2 个数为不同的最好的三角汉密尔顿的数目。如果地图中不存在汉密尔
顿路径，则输出0 0。
注意：一条路径可以以相反的顺序来表示，但这与原来的路径是同一条路径。
在算法中用二进制位表示路径状态。比如如果有3 个岛，则用二进制的111 表示一条汉密尔
顿路径。算法中记录某条路径最后的两个岛，因为这两个岛可决定加入新岛时的三角权值。这样，
状态转移方程将是一个三维数组：dp[status][last_but_one_island][last_island]，与之对应的还有
路径数：ways[status][last_but_one_island][last_island]。
当前路径加入一个点后，状态无疑会变大，因此，状态转移时从小到大进行处理。初始化时，
状态中包含两个岛的状态函数需要被初始化为两岛权值之以及加上桥梁权值，对应的路径应为1。
状态转移时，对当前状态考虑所有可能的最后两个岛，并考虑所有可能加入的岛，从而可以生成
新的状态。路径数随之更新。
需要注意的是，dp 和ways 的值可能会比较大，因此要用64 位长整型来表示。另外，要考虑
只存在一个岛的情况。只有一个岛的情况无疑是存在最好三角汉密尔顿路径的。
最后，由于桥梁是双向的，一条路径存在顺序与逆序两种表示方式，而算法中对于方向相反
的两条路径是视为不同路径的，因此最后求得的路径数目需要除以2。
顿路径。算法中记录某条路径最后的两个岛，因为这两个岛可决定加入新岛时的三角权值。这样，
状态转移方程将是一个三维数组：dp[status][last_but_one_island][last_island]，与之对应的还有
路径数：ways[status][last_but_one_island][last_island]。
当前路径加入一个点后，状态无疑会变大，因此，状态转移时从小到大进行处理。初始化时，
状态中包含两个岛的状态函数需要被初始化为两岛权值之以及加上桥梁权值，对应的路径应为1。
状态转移时，对当前状态考虑所有可能的最后两个岛，并考虑所有可能加入的岛，从而可以生成
新的状态。路径数随之更新。
需要注意的是，dp 和ways 的值可能会比较大，因此要用64 位长整型来表示。另外，要考虑
只存在一个岛的情况。只有一个岛的情况无疑是存在最好三角汉密尔顿路径的。
最后，由于桥梁是双向的，一条路径存在顺序与逆序两种表示方式，而算法中对于方向相反
的两条路径是视为不同路径的，因此最后求得的路径数目需要除以2。
#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
__int64 dp[1<<13][14][14];//dp[s][i][j]从i岛到j岛到达s状态的最大价值
__int64 ways[1<<13][14][14];//ways[s][i][j]记录从从i到j到s状态的路径数
__int64 maxw,maxv;//记录最大价值和对应的路径数
bool link[14][14];//link[i][j]记录i岛和j岛是否相通
int value[14],n,m;//value记录每个岛的价值n,m如题意
int main()
{
int q,s,i,j,k,a,b,news,temp;//s遍历各种状态。news记录新状态
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&n,&m);
for(i=0; i<n; i++)
scanf("%d",value+i);
memset(dp,-1,sizeof dp);//初始化
memset(ways,0,sizeof ways);
memset(link,0,sizeof link);
for(i=0; i<m; i++)
{
scanf("%d%d",&a,&b);
a--,b--;
link[a][b]=true;
link[b][a]=true;
dp[(1<<a)|(1<<b)][a][b]=value[a]+value[b]+value[a]*value[b];//初始为两岛的和和乘积
dp[(1<<b)|(1<<a)][b][a]=value[a]+value[b]+value[a]*value[b];
ways[(1<<a)|(1<<b)][a][b]=1,ways[(1<<b)|(1<<a)][b][a]=1;//路径初始为1
}
if(n==1)//处理只有一个岛的情况
{
printf("%d 1\n",value[0]);
continue;
}
for(s=0; s<(1<<n); s++)//从小到大进行状态转移，并做路径压缩
{
for(i=0; i<n; i++)//枚举第一点
{
if(!(s&(1<<i)))//s状态是i走到j在走到k产生的所以对应位置必须为1
continue;
for(j=0; j<n; j++)//枚举第二点
{
if(i==j)//不用解释。第一点和第二点相同无意义
continue;
if(!(s&(1<<j)))//对应位置必须为1
continue;
if(dp[s][i][j]<0)//状态不合法
continue;
for(k=0; k<n; k++)//枚举终点
{
if(s&(1<<k))//对应位置必须为1
continue;
if(!link[j][k])//第二点和终点必须相连
continue;
temp=dp[s][i][j]+value[k]+value[j]*value[k];
if(link[i][k])//如果能构成三角形
temp+=value[i]*value[j]*value[k];
news=s|(1<<k);//新状态是这么得来的。说明更新状态需要用到较小状态所以可以递推。算法可行
if(temp==dp[news][j][k])//如果值一样就加路径否则更新
ways[news][j][k]+=ways[s][i][j];
else if(temp>dp[news][j][k])
{
ways[news][j][k]=ways[s][i][j];
dp[news][j][k]=temp;
}
}
}
}
}
maxv=-1;
maxw=0;
news=(1<<n)-1;//记录合法的最终状态
for(i=0; i<n; i++)//同上枚举
for(j=0; j<n; j++)
{
if(!link[i][j])//必须相连
continue;
if(dp[news][i][j]>maxv)//更新
{
maxv=dp[news][i][j];
maxw=ways[news][i][j];
}
else if((dp[news][i][j]==maxv))//加路径
maxw+=ways[news][i][j];
}
maxw/=2;//正向路径与反向路径记作同一条路经去除重复的
printf("%I64d %I64d\n",maxv==-1?0:maxv,maxw);
}
return 0;
}