#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 14;const int INF = INT_MAX / 3;int n,m,dist[maxn][maxn];LL v[maxn];LL f[maxn][maxn][1 << 14];LL cnt[maxn][maxn][1 << 14];void solve() {    memset(f,-1,sizeof(f));    memset(cnt,0,sizeof(cnt));    int maxstate = (1 << n) - 1; //init    for(int i = 0;i < n;i++) {        for(int j = 0;j < n;j++) if(dist[i][j]) {            int s = (1 << i) | (1 << j);            f[i][j][s] = v[i] * v[j] + v[i] + v[j];            cnt[i][j][s] = 1;        }    }    //dp    LL ans = 0,ct = 0;    for(int s = 0;s <= maxstate;s++) {        for(int i = 0;i < n;i++) if(s & (1 << i)) {            for(int j = 0;j < n;j++) if(dist[i][j] && (s & (1 << j)) && f[i][j][s] != -1) {                for(int k = 0;k < n;k++) if(dist[j][k] && !(s & (1 << k))) {                    int ns = s | (1 << k);                    LL &nowstate = f[i][j][s],&nextstate = f[j][k][ns];                    LL &nowcnt = cnt[i][j][s],&nextcnt = cnt[j][k][ns];                    LL addv = v[j] * v[k] + v[k];                    if(dist[i][k]) addv += v[i] * v[j] * v[k];                    if(nowstate + addv > nextstate) {                        nextstate = nowstate + addv;                        nextcnt = nowcnt;                    }                    else if(nowstate + addv == nextstate) {                        nextcnt += nowcnt;                    }                }                if(s == maxstate) {                    if(f[i][j][s] > ans) {                        ans = f[i][j][s];                        ct = cnt[i][j][s];                    }                    else if(f[i][j][s] == ans) {                        ct += cnt[i][j][s];                    }                }            }        }    }    if(ans == 0) cout << "0 0" << endl;    else cout << ans << " " << ct / 2 <<  endl;}int main() {    //freopen("in.txt","r",stdin);    int T; scanf("%d",&T);    while(T--) {        memset(dist,0,sizeof(dist));        scanf("%d%d",&n,&m);        for(int i = 0;i < n;i++) cin >> v[i];        for(int i = 0;i < m;i++) {            int a,b; cin >> a >> b;            a--; b--;            dist[a][b] = dist[b][a] = 1;        }        if(n == 1) cout << v[0] << " " << 1 << endl;        else solve();    }    return 0;}

  1 #include <cstdio>  2 #include <sstream>  3 #include <fstream>  4 #include <cstring>  5 #include <iostream>  6 #include <algorithm>  7 #include <map>  8 #include <cctype>  9 #include <ctime> 10 #include <set> 11 #include <climits> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <cstdlib> 16 #include <cmath> 17 #include <string> 18 #include <list> 19  20 #define INPUT_FILE "in.txt" 21 #define OUTPUT_FILE "out.txt" 22  23 using namespace std; 24  25 typedef long long LL; 26 const int INF = INT_MAX / 2; 27  28 void setfile() { 29     freopen(INPUT_FILE,"r",stdin); 30     freopen(OUTPUT_FILE,"w",stdout); 31 } 32  33 const int maxn = 13; 34  35 int n,maxstate; 36 LL w[maxn][maxn],c[maxn]; 37 LL note[maxn][maxn][1 << 13]; 38 LL cnt[maxn][maxn][1 << 13]; 39  40 LL dfs(int prev,int now,int state) { 41     if(state == maxstate) return note[prev][now][state] = 0; 42     LL ret = -1,nret;  43     if(note[prev][now][state] != -1) { 44         return note[prev][now][state]; 45     } 46     for(int i = 0;i < n;i++) { 47         if((state & (1 << i)) == 0 && w[now][i] != -1) { 48             LL addv = w[now][i] + c[i]; 49             if(w[prev][i] != -1) addv += c[i] * c[prev] * c[now]; 50             nret = dfs(now,i,state | (1 << i)) + addv; 51             if(nret > ret) { 52                 ret = nret; 53             } 54         } 55     } 56     if(ret == -1) return -INF * 100000LL; 57     return note[prev][now][state] = ret; 58 } 59  60 LL getcount(int prev,int now,int state) { 61     if(state == maxstate) return 1; 62     if(cnt[prev][now][state] != -1) return cnt[prev][now][state]; 63     LL ret = 0; 64     for(int i = 0;i < n;i++) { 65         if((state & (1 << i)) == 0 && w[now][i] != -1) { 66             LL addv = w[now][i] + c[i]; 67             if(w[prev][i] != -1) addv += c[i] * c[prev] * c[now]; 68             if(note[prev][now][state] == note[now][i][state | (1 << i)] + addv) { 69                 ret += getcount(now,i,state | (1 << i)); 70             } 71         } 72     } 73     return cnt[prev][now][state] = ret; 74 } 75  76 int main() { 77     int T; 78     cin >> T; 79     while(T--) { 80         memset(w,-1,sizeof(w)); 81         memset(cnt,-1,sizeof(cnt)); 82         memset(note,-1,sizeof(note)); 83         int m; 84         cin >> n >> m; 85         for(int i = 0;i < n;i++) { 86             cin >> c[i]; 87         } 88         for(int i = 0;i < m;i++) { 89             int u,v; 90             cin >> u >> v; 91             u--; v--; 92             w[u][v] = w[v][u] = c[u] * c[v]; 93         } 94         maxstate = (1 << n) - 1; 95         LL ans = 0,ccnt = 0; 96         for(int i = 0;i < n;i++) { 97             for(int j = 0;j < n;j++) if(i != j && w[i][j] != -1) { 98                 LL ret = dfs(i,j,(1<<i)|(1<<j)) + w[i][j] + c[i] + c[j]; 99                 ans = max(ans,ret);100             }101         }102         for(int i = 0;i < n;i++) {    103             for(int j = 0;j < n;j++) {104                 if(note[i][j][(1 << i)|(1 << j)] + w[i][j] + c[i] + c[j] == ans) {105                     ccnt += getcount(i,j,(1<<j)|(1<<i));106                 }107             }108         }109         if(n == 1) cout << c[0] << " " << 1 << endl;110         else if(ccnt == 0) cout << "0 0" << endl;111         else cout << ans << " " << ccnt / 2 << endl;112     }113     return 0;114 }