D - General Weighted Max Matching
题意
给定无向图，边有边权。让你选择一组边，满足任意两边不相交且总边权和最大。
顶点数 $\le 16 $
思路
状压 DP 求解该问题
状态：利用 n 位二进制表示每个顶点是否已经被选择，0 表示该顶点未选，1 表示当前顶点已选
转移：每一个二进制数表示的状态可以通过加入新的边进行转移
边是否选择与点是否选择等价，且我们不关心之前怎么选的边，只关心新加边如何转移，以及之前加的边对于答案的影响
代码
void solve(){
int n;
cin >> n;
vector d(n, vector<int>(n, 0));
for(int i = 0; i < n; ++ i){
for(int j = i + 1; j < n; ++ j){
cin >> d[i][j];
}
}
vector<ll> dp(1 << n, 0);
for(int b = 0; b < (1 << n); ++ b){//枚举状态
int l = -1;
for(int i = 0; i < n; ++ i){
if(!(b >> i & 1)){
l = i; break;
}
}
for(int i = 0; i < n; ++ i){
if(!(b >> i & 1)){//转移
int nb = b | (1 << l) | (1 << i);
dp[nb] = max(dp[nb], dp[b] + d[l][i]);
}
}
}
cout << dp[(1 << n) - 1] << '\n';
return ;
}