poj2288 Islands and Bridges

英文题面

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.

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 ViVi+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 ViVi+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.
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’.

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
Shanghai 2004

题目大意

求包含n个点的哈密顿路径,对于路径上每一个点,它对路径的贡献为vi,每一对相邻的点(路径上),贡献为ai aj, 两两相邻的三个点,贡献为ai aj * ak,求权值最大的包含n个点的哈密顿路径,以及有多少条这样的路径.

分析

   n的数据范围这么小,很显然可以用状压dp解决.
   令$f(i,j,k)$表示状态为i,上一次选的点为j,当前选的点为k的最大权值,$g(i,j,k)$则表示相应的方案数. 为何要这么设计状态?第一维是因为状压dp状态的必要性,第二、三维是因为需要知道当前要从哪个点出发(用来判是否连通以计算权值).转移什么的都挺好想的. 枚举在i中的两个点j,k和不在i中的一个点l,用$f(i,j,k)$来更新$f(i | (1 << l),k,l)$,至于如何求方案数,那就是固定的套路啦. 如果最大值更新了,那么方案数直接边,如果更新的最大值等于原来的最大值,方案数直接累加即可.
  几个坑点:

  • 转移的时候一定要判断状态的合法性,即$f(i,j,k)$不能为-1.
  • 有可能只有一个点.
  • 我一开始以为最后所有的点的权值都会被累加进入答案,于是对这一部分单独进行的处理. 事实上会出现没有哈密顿路径的情况,如果单独处理会输出错误的答案(将所有点的权值和给输出了).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93

    #include <cstring>
    #include <iostream>
    #include <algorithm>

    using namespace std;

    typedef long long ll;
    ll Q,n,m,a[21],f[(1 << 14)][15][15],g[(1 << 14)][15][15],b[21][21],sum,maxn,ans;

    void ()
    {
    memset(f,-1,sizeof(f));
    memset(g,0,sizeof(g));
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++)
    if (b[i][j])
    {
    ll temp = (1 << (i - 1)) | (1 << (j - 1));
    f[temp][i][j] = a[i] * a[j];
    g[temp][i][j] = 1;
    }
    for (ll i = 0; i <= maxn; i++)
    for (ll j = 1; j <= n; j++)
    if ((1 << (j - 1)) & i)
    for (ll k = 1; k <= n; k++)
    if (((1 << (k - 1)) & i) && b[j][k] && f[i][j][k] != -1)
    for (ll l = 1; l <= n; l++)
    if (!((1 << (l - 1)) & i) && b[k][l] && l != j)
    {

    ll temp = f[i][j][k] + a[k] * a[l];
    if (b[j][l])
    temp += a[k] * a[l] * a[j];
    if (temp > f[i | (1 << (l - 1))][k][l])
    {
    f[i | (1 << (l - 1))][k][l] = temp;
    g[i | (1 << (l - 1))][k][l] = g[i][j][k];
    }
    else if (temp == f[i | (1 << (l - 1))][k][l])
    g[i | (1 << (l - 1))][k][l] += g[i][j][k];
    }
    ll maxx = 0;
    ans = 0;
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++)
    if (b[i][j])
    {
    if (f[maxn][i][j] > maxx)
    {
    maxx = f[maxn][i][j];
    ans = g[maxn][i][j];
    }
    else
    if (f[maxn][i][j] == maxx)
    ans += g[maxn][i][j];
    }
    if (maxx == 0)
    cout << 0 << " " << 0 << endl;
    else
    printf("%lld %lldn",maxx + sum,ans / 2);
    }

    int main()
    {
    scanf("%lld",&Q);
    while (Q--)
    {
    sum = 0;
    memset(b,0,sizeof(b));
    scanf("%lld%lld",&n,&m);
    maxn = (1 << n) - 1;
    for (ll i = 1; i <= n; i++)
    {
    scanf("%lld",&a[i]);
    sum += a[i];
    }
    if (n == 1)
    {
    cout << a[1] << " " << 1 << endl;
    continue;
    }
    for (ll i = 1; i <= m; i++)
    {
    ll x,y;
    scanf("%lld%lld",&x,&y);
    b[x][y] = b[y][x] = 1;
    }
    solve();
    }

    return 0;
    }