[ABC318D] General Weighted Max Matching 题解
[ABC318D] General Weighted Max Matching 题解
题意
给定无向有权完全图，求最大权匹配。
思路分析
注意到 \(n \le 16\)，我考虑状压 DP。
设当前点集 \(S\) 中最大权匹配的答案是 \(f_S\)，我们考虑 \(S\) 中“最后”一个点 \(p\)（这里的“最后”一个点是指，在状压表示状态的时候，最后一个 1 所代表的那个点，只需从这个点考虑就行，不需要考虑其他前面的点，因为会被更小状态考虑过）。
我们可以从前面其他点中，选择一个点 \(q\) 和这个点匹配，也可以不匹配这个点。于是有转移方程：
\[f_S = \max(f_{S-p},f_{S-p-q}),p \in S,q \in S, p \ne q
\]
其中 \(w_{p,q}\) 代表点 \(p\) 与点 \(q\) 之间的边权。
初始化：当 \(S\) 中没有点或只有一个点的时候 \(f_S = 0\)；当 \(S\) 中有两个点 \(u,v\) 时，\(F_S = w_{u,v}\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 18;
const int S = (1<<(N+1));
LL a[N][N];
LL dp[S];
LL cnt[S];
LL n;
int count(int s)
{
if(cnt[s] != -1)
return cnt[s];
int ans = 0;
while(s>0)
{
ans += (s&1);
s >>= 1;
}
return cnt[s] = ans;
}
LL dfs(int s)
{
if(dp[s] != -1) return dp[s];
if(count(s) <= 1)
{
dp[s] = 0;
return 0;
}
if(count(s) == 2)
{
int idx1 = -1,idx2 = -1;
int tmp = s,tmpidx = 0;
while(tmp>0)
{
if(tmp&1)
{
if(idx1 == -1)
{
idx1 = tmpidx;
}
else
{
idx2 = idx1;
idx1 = tmpidx;
}
}
tmpidx++;
tmp >>= 1;
}
dp[s] = a[idx1][idx2];
return dp[s];
}
LL idxf = -1;
LL ans = 0;
for(int i = n-1;i >= 0;i--)
{
if((s&(1<<i)) > 0)
{
if(idxf == -1)
{
idxf = i;
}
else
{
ans = max(ans,a[idxf][i]+dfs(s-(1<<i)-(1<<idxf)));
}
}
}
ans = max(ans,dfs(s-(1<<idxf)));
return dp[s] = ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(dp,-1,sizeof(dp));
memset(cnt,-1,sizeof(cnt));
cin >> n;
for(int i = 1;i <= n;i++)
{
for(int j = i+1;j <= n;j++)
{
cin >> a[i-1][j-1];
a[j-1][i-1] = a[i-1][j-1];
}
}
dfs((1<<n)-1);
cout << dp[(1<<n)-1] << "\n";
return 0;
}