[POJ - 2288] Islands and Bridges

发表于 | 分类于 ， ，
本文字数： 18k

链接

\(\text{POJ - 2288 Islands and Bridges}\)

题意

  这里有\(n\)个城市，定义最好的三角哈密顿路径为\(value\)值最大的哈密顿路径，\(value\)产生于三部分，如果经过某个城市\(x\)那么这个城市将贡献\(value_x\)，如果经过连续两个城市\(x、y\)，那么将贡献\(value_x*value_y\)，如果经过连续三个城市\(x、y、z\)，那么将贡献\(value_x*value_y*value_z\)，这里说的连续不是说城市编号连续，需要你求出这个图的三角哈密顿路径的长度，以及它的个数；

  数据范围：\(1\leq n\leq 13,value_i\leq 100\).

分析

  三角的意思是，\(i\)可以到\(j\)，\(j\)可以到\(k\)，\(k\)可以到\(i\)，由于我们需要求连续三个城市的贡献，所以我们需要开一个三维的数组\(dp[s][i][j]\)，其中\(s\)表示到达\(i\)的当前的状态，\(i\)的前一个经过的点是\(j\)，同样的还需要一个数组\(num[s][i][j]\)来记录哈密顿路径的个数；

  首先初始化\(num\)为0，及\(dp[(1<<i)|(1<<j)][i][j]=value_i+value_j+value_i*value_j\)，\(i、j\)为任意两个城市，\(i、j\)不相等；

  枚举状态s，以及三个点\(i、j、k\)，考虑从上一个点\(j\)转移到当前点\(i\)，而\(j\)的上一个点为\(k\)，考虑从上一个状态转移过来，那么假设当前状态为\(s\)，则有\(dp[s][i][j]=\max dp[s\space xor\space (1<<i)][j][k]\)，主要判断\(i、j、k\)是否可以组成三角形，若可以还需要把\(dp[s][i][j]\)加上\(value_x*value_y*value_z\)，关于数量的计算，看\(dp[s][i][j]\)是否能够通过之前的状态更新，若能更新，就令当前数量等于上一个转移过来的状态的数量，若二者相等，就把之前的状态的数量加到当前的状态的数量上，具体见代码；

  需要注意的是，在转移的过程中还需要判断之前的那个状态是否是有效的状态，即存在这样的情况，现在的状态是s，之前的状态\(p\)，虽然它的\(j、k\)位都是1，\(i\)位是1，但是这个状态\(p\)并不能通过\(p\)之前的任意一个可行状态转移过来，所以状态\(p\)的值还是初始的时候我们初始化的值；对于这种情况我们就需要判断\(dp[s^(1<<i)][j][k]\)的状态；自己写的时候，第一次没注意\(int\)，之后改成\(long\space long\)，还是\(wa\)，然后不知哪错，疯狂交，疯狂\(wa\)，看了一个小时才找到问题。以后要注意，这里出现这样的原因，应该是图的原因，给出的图不一定是个完全图，某些边是不连通的。

代码

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
94
95
96
97
98
99
#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define mod 998244353
#define inf 0x3f3f3f3f
#define maxn 500005
#define N 300005
typedef long long ll;

inline int read()
{
    int x = 0;
    int f = 1;
    char c = getchar();
    while (c<'0' || c>'9')
    {    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

ll q, n, m, dp[1 << 14][15][15], num[1 << 14][15][15], val[15], e[15][15];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> q;
    while (q--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> val[i];
        int a, b;
        memset(e, 0, sizeof(e));
        for (int i = 0; i < m; i++) {
            cin >> a >> b;
            a--, b--;
            e[a][b] = e[b][a] = 1;
        }
        if (n == 1) {
            cout << val[0] << " " << 1 << endl;
            continue;
        }
        memset(dp, 0, sizeof(dp));
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) {
                if (i == j || !e[i][j]) continue;
                dp[(1 << i) | (1 << j)][i][j] = val[i] + val[j] + val[i] * val[j];
                num[(1 << i) | (1 << j)][i][j] = 1;
            }
        for (int s = 0; s < 1 << n; s++)
            for (int i = 0; i < n; i++)
                if ((s >> i) & 1) {
                    for (int j = 0; j < n; j++) {
                        if (!e[i][j] || !((s >> j) & 1) || i == j) continue;
                        for (int k = 0; k < n; k++) {
                            if (!((s >> k) & 1) || !e[j][k]||k == i || j == k) continue;
                            if (!dp[s ^ (1 << i)][j][k]) continue;
                            ll temp = dp[s ^ (1 << i)][j][k] + val[i] + val[i] * val[j];
                            if (e[i][k]) temp += val[i] * val[j] * val[k];
                            if (temp > dp[s][i][j]) {
                                dp[s][i][j] = temp;
                                num[s][i][j] =  num[s ^ (1 << i)][j][k];
                            }else if (temp == dp[s][i][j]) {
                                num[s][i][j] +=  num[s ^ (1 << i)][j][k];                                
                            }
                        }
                    }
                }
        ll ans = 0,cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (i == j || !e[i][j]) continue;
                if (ans < dp[(1 << n) - 1][i][j]) {
                    ans = dp[(1 << n) - 1][i][j];
                    cnt = num[(1 << n) - 1][i][j];
                }else if (ans == dp[(1 << n) - 1][i][j]){
                    cnt += num[(1 << n) - 1][i][j];
                }
            }
        cout << ans << " " << cnt / 2<< endl;
    }
}