题目描述

/*
1194 岛和桥 islands and bridges
类似最长汉密尔顿路径，三种数据的最大和
1、每个岛屿的权值之和。（可预处理，最后加入答案，因为每条路径的点权和相同） 
2、汉密尔顿路径中，每一条边连接的相邻岛屿的权值乘积之和。 
3、如果在汉密尔顿路径中存在相邻的三个岛屿可以构成环形，
    则将所有满足条件的相邻岛屿三元组权值的乘积相加求和。

预处理任意两点之间直接到达的点权值之积，若为0说明不直接相连 

因为涉及到三元组，连续三个点，所以需要在压位状态值之外还需要设定两维
    第一维是当前状态在哪个点结束，第二维上一轮是哪个点结束
如果超过之前到达这个状态的最大值，则刷新 
    f[i][j][k].first = f[ij][k][l].first + r[k][j] + (r[j][l]?r[j][l]*a[k]:0)
    i状态             i状态减j           k和j的关系值     如果存在三点回路                    
    f[i][j][k].second = f[ij][k][l].second;
    路径条数 
如果和之前到达这个状态的最大值相等，则路径条数+1 
    f[i][j][k].second += f[ij][k][l].second;
    路径条数

新增了一个虚拟的n点，确定初始点0~n-1时，前导点设为n，路径值为0，条数为1
后续只要根据情况刷新最大值即可。 
用时：1110 ms
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
pair<int,int> f[1<<N][N][N], ans;
int a[N], r[N][N];
int T, n, m;
int main(){
    cin >> T;
    while(T--){
        cin >> n >> m;
        int sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            sum += a[i];        //预处理最后可能需要输出的全部点权和 
        }
        memset(r, 0, sizeof(r));    //关系值初始化 
        for(int i = 0; i < m; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            x--, y--;
            r[x][y] = r[y][x] = a[x]*a[y];  //直接记录点权乘积，节省时间 
        }

        ans = make_pair(0, 0);              //答案初始化 
        memset(f, 0x80, sizeof(f));         //状态值初始设为很小 
        for(int start = 0; start < n; start++){         //起点值初始化 
            f[1<<start][start][n] = make_pair(0, 1);    //路径值为0，条数为1 
        }
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < n; j++){                 //尝试终点为j 
                if(!(i >> j & 1)) continue;             //终点位j位必须是1 
                int ij = i ^ (1<<j);                    //扣除j位 
                for(int k = 0; k < n; k++){
                    if(!r[k][j]) continue;              //前一位k必须和j相邻 
                    if(!(ij >> k & 1)) continue;        //前一位k位必须是1 
                    int ijk = ij ^ (1<<k) ^ (1<<n);     //扣除k位,加上第n位（初始需要） 
                    for(int l = 0; l <= n; l++){        //再前一位l 
                        if(!(ijk>>l & 1)) continue;     //再前一位l位必须是1 
                        int tmp = f[ij][k][l].first + r[k][j] + (r[j][l]?r[j][l]*a[k]:0);
                        if(f[i][j][k].first < tmp){     //更优，全部更新 
                            f[i][j][k].first = tmp;
                            f[i][j][k].second = f[ij][k][l].second;
                        }else if(f[i][j][k].first == tmp){  //和最大值相同，增加条数 
                            f[i][j][k].second += f[ij][k][l].second;
                        }
                    }
                }
            }
        }
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){ //走满全部点，看结果和答案比较 
                if(ans.first < f[(1<<n)-1][j][k].first){
                    ans = f[(1<<n)-1][j][k];
                }else if(ans.first == f[(1<<n)-1][j][k].first){
                    ans.second += f[(1<<n)-1][j][k].second;
                }
            }
        }
        if(ans.second)cout << ans.first+sum << " " << ans.second/2 << endl; //路径不能和来回相等，即一半 
        else cout << "0 0" << endl;     //无解则为0 
    }
    return 0;
}


//提高效率：还可以通过lowbit优化，快速访问最低的1位置 
//用时：970 ms，差别不大 
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
pair<int,int> f[1<<N][N][N], ans;
int a[N], r[N][N];
int T, n, m;
int wei[1<<N];      //每个权值位的位置 
int main(){
    for(int i = 0; i < N; i++){
        wei[1<<i] = i;
    }               //预处理每个权值位的位置  
    cin >> T;
    while(T--){
        cin >> n >> m;
        int sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            sum += a[i];
        }
        memset(r, 0, sizeof(r));
        for(int i = 0; i < m; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            x--, y--;
            r[x][y] = r[y][x] = a[x]*a[y];
        }

        ans = make_pair(0, 0);
        memset(f, 0x80, sizeof(f));
        for(int start = 0; start < n; start++){
            f[1<<start][start][n] = make_pair(0, 1);
        }
        for(int i = 0; i < 1<<n; i++){
            int lowbiti;
            for(int ti = i; ti; ti -= lowbiti){ //lowbiti 
                int j = wei[lowbiti= ti&-ti];
                int ij = i ^ (1<<j);
                int lowbitij;
                for(int tij = ij; tij; tij -= lowbitij){    //lowbitij
                    int k = wei[lowbitij = tij&-tij];
                    if(!r[k][j]) continue;
                    int ijkn = ij ^ (1<<k) ^ (1<<n); 
                    int lowbitijkn;
                    for(int tijkn = ijkn; tijkn; tijkn -= lowbitijkn){  //lowbitijkn
                        int l = wei[lowbitijkn = tijkn&-tijkn];
                        int tmp = f[ij][k][l].first + r[k][j] + (r[j][l]?r[j][l]*a[k]:0);
                        if(f[i][j][k].first < tmp){
                            f[i][j][k].first = tmp;
                            f[i][j][k].second = f[ij][k][l].second;
                        }else if(f[i][j][k].first == tmp){
                            f[i][j][k].second += f[ij][k][l].second;
                        }
                    }
                }
            }
        }
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(ans.first < f[(1<<n)-1][j][k].first){
                    ans = f[(1<<n)-1][j][k];
                }else if(ans.first == f[(1<<n)-1][j][k].first){
                    ans.second += f[(1<<n)-1][j][k].second;
                }
            }
        }
        if(ans.second)cout << ans.first+sum << " " << ans.second/2 << endl;
        else cout << "0 0" << endl;
    }
    return 0;
}
/*
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

22 3
69 1
*/