写题解的效率好低啊QvQ补题的速度好慢啊
Description
题目链接: https://www.zhixincode.com/contest/12/problem/D?problem_id=186
题意是给定一幅无向带权连通图，询问保证连通的前提下，删除一些边使得道路复杂度 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}d(i,j)$ 的值最大（$d(i,j)$ 表示 $i$ 到 $j$ 的最短路径），求这个最大值
Solution
容易看出的一点是，满足题意的图必定是颗生成树，如果不是树的话，删除某条边必能在保证连通的条件下增大道路复杂度(也可能不变)
$n$ 的范围只有 $14$，我们可以考虑一个状压dp
记 $dp[S][i]$ 为 $S$ 状态下以 $i$ 为根的树的最优解，可以将这个树分解成 $T$ 状态下以 $j$ 为根的子树和 $S-T$ 状态下以 $i$ 为根的子树，$i$ 和 $j$ 所连的边能产生的贡献即为边权乘上 $j$ 子树大小和剩余点集的大小
转移方程可以写作:
$dp[S][i]=max(dp[S][i],dp[S-T][i]+dp[T][j]+a[i][j]*size(T)*(n-size(T))$
$dp[(1«n)-1][0]$ 即为题目所求
总体复杂度为: $O(3^n*n^2)$
如果把状态跑满的话会 T…所以需要剪一下枝
枚举 $j$ 的时候可以通过 $S$ 不停地减 $lowbit$ 来进行，会比 $for$ 循环枚举 1~n 快很多
AC code
Time: 718ms
Memory: 5MB
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
#include<bits/stdc++.h>
using namespace std;
#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&-x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=14;
ll dp[(1<<maxn)][maxn];
int n,m;
int a[maxn][maxn];
int sz[(1<<maxn)];
int pre[(1<<maxn)];
int main() {
scanf("%d%d",&n,&m);
mem(a,0);
rep(i,1,m) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u--; v--;
a[u][v]=a[v][u]=w;
}
rep(S,0,(1<<n)-1) {
rep(i,0,n-1) {
if((S>>i)&1) sz[S]++;
dp[S][i]=-INF;
}
}
rep(i,0,n-1) pre[1<<i]=i;
rep(S,1,(1<<n)-1) {
for(int t=S;t;t-=lowbit(t)) {
int i=pre[lowbit(t)];
if(sz[S]==1) {
dp[S][i]=0; continue;
}
int P=S^(1<<i);
for(int T=P;T;T=(T-1)&P) {
for(int p=T;p;p-=lowbit(p)) {
int j=pre[lowbit(p)];
if(a[i][j]) dp[S][i]=max(dp[S][i],dp[T][j]+dp[S-T][i]+1ll*a[i][j]*sz[T]*(n-sz[T]));
}
}
}
}
ll ans=0;
rep(i,0,n-1) ans=max(ans,dp[(1<<n)-1][i]);
printf("%lld\n",ans);
return 0;
}