大致题意： 给你一张图，定义(dis(i,j))为(i)与(j)的最短距离，现要求删去若干条边，使得图仍然联通，且(sum_{i=1}^nsum_{j=i+1}^ndis(i,j))最大。
一个贪心的思想
考虑到要使点与点间的距离最大，则多删边肯定是更优的。
又考虑图必须联通，则最后的图肯定是一棵树。
状压(DP)
看到数据范围如此之小（(Nle14)），自然会想到状压(DP)啦。
我们可以设(f_{i,x})表示子集(i)在强制以(x)为根的情况下的最优解（易证此题局部最优解即为全局最优解），注意这里我们强制除根以外的节点不能向外连边。并设(g_i)表示子集(i)内的元素个数。
考虑如何转移。
对于这种子集(DP)，一般套路都是枚举(i)的一个子集(j)来将其分成(j)和(i ext{^}j)（记为(k)）两部分。
这题也不例外。
我们可以枚举一个属于(j)的点(x)，然后枚举一个属于(k)的点(y)，表示将(x)作为根，且在(x)与(y)之间连边合并两个子集。
考虑到前面我们对根的定义，则此后(y)的子树内的节点不可能再向外连边，即其他节点必定在靠近(x)的同一侧。
那我们就可以计算出这条边被经过的次数应为(g_k*(n-g_k))，从而得到这条边的贡献，并由此推出转移方程：
[f_{i,x}=max(f_{i,x},f_{j,x}+f_{k,y}+g_k*(n-g_k)*v_{x,y})
]
其中(v_{x,y})表示(x)和(y)两点间的边权。
具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 14
#define M 91
#define LL long long
#define swap(x,y) (x^=y^=x^=y)
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define pb push_back
using namespace std;
int n,m,g[1<<N],v[N+5][N+5];LL f[1<<N][N+5];vector<int> p[1<<N];
int main()
{
RI i,j,k,l,x,y,z,tj,tk;Reg LL ans=0;
for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&z),v[x][y]=v[y][x]=z;//读入+建边
for(l=1<<n,i=1;i^l;++i) for(g[i]=g[i>>1]+(i&1),j=1;j<=n;++j) (i>>j-1)&1&&(p[i].pb(j),f[i][j]=g[i]^1?-1:0);//初始化g数组以及f数组，用p来存储每个子集所包含的元素
for(i=1;i^l;++i) for(j=(i-1)&i;j;j=(j-1)&i)//枚举i，然后枚举它的子集j
{
for(k=i^j,tj=0;tj^g[j];++tj) if(~f[j][x=p[j][tj]]) for(tk=0;tk^g[k];++tk)//枚举一个属于j的点x和属于k的点y
if(~f[k][y=p[k][tk]]&&v[x][y]) Gmax(f[i][x],f[j][x]+f[k][y]+1LL*g[k]*(n-g[k])*v[x][y]);//判断情况是否合法后转移
}for(i=1;i<=n;++i) Gmax(ans,f[l-1][i]);//求出最优的答案
return printf("%lld",ans),0;//输出答案
}