T23:General Weighted

题目意思

从 N 个点中选若干条边，要求选到的边两两不共用端点（匹配）。求这些边的长度和的最大值。

---

思路解析

用二进制 mask 表示一个点集（哪些点参与考虑）。

• dp[mask]：只在 mask 这批点里面选边，能得到的最大总长度。
• 基础：如果 mask 里只有两个点 u,v，那么 dp[mask] = D[u][v]（只选这一条边）。
• 转移：对一个偶数个点的 mask，任选两点 u,v 配成一条边，剩余部分继续最优：
  • dp[mask] = max(dp[mask], dp[mask^(1<<u)^(1<<v)] + dp[(1<<u)|(1<<v)])
• 最终答案：
  • 如果 N 是偶数，答案是 dp[ALL]
  • 如果 N 是奇数，可以去掉任意一个点不参与：答案是 max(dp[ALL^(1<<i)])

---

正确代码

#include <bits/stdc++.h>
using namespace std;

#define int long long                                     // 使用long long避免边权相加溢出

int n;                                                   // 点数
int dp[1<<16];                                           // dp[mask]：mask内最大匹配权值
int t;                                                   // 临时mask
int ans;                                                 // 最终答案
int a;                                                   // 读入的边权

int cntbit(int x){                                       // 计算x的二进制1的个数
    int c=0;                                             // 计数器初始化
    while(x){                                            // 直到x变成0
        if(x&1)c++;                                      // 若最低位为1则计数+1
        x>>=1;                                           // 右移一位
    }
    return c;                                            // 返回1的个数
}

signed main(){                                           // 主函数入口
    ios::sync_with_stdio(false);                         // 加速输入输出
    cin.tie(nullptr);                                    // 加速输入输出

    cin>>n;                                              // 读入n

    for(int i=0;i<(1<<n);i++)dp[i]=0;                    // dp初始化为0（不选边时价值为0）

    for(int i=1;i<n;i++){                                // 读入上三角边权
        for(int j=i+1;j<=n;j++){                         // i<j
            cin>>a;                                      // 读入D(i,j)
            int mask=(1<<(i-1))|(1<<(j-1));              // 只包含i和j的mask
            dp[mask]=a;                                  // 两点集合的最优就是这条边
        }
    }

    vector<int> masks;                                   // 存所有“点数为偶数且非0”的mask
    masks.reserve(1<<n);                                 // 预留空间减少扩容

    for(int mask=1;mask<(1<<n);mask++){                  // 枚举所有非空mask
        int c=cntbit(mask);                              // 计算mask中点的数量
        if(c%2==0)masks.push_back(mask);                 // 只有偶数个点才可能完全两两配对
    }

    for(int idx=0;idx<(int)masks.size();idx++){          // 枚举所有偶数点的mask做转移
        int mask=masks[idx];                             // 当前mask
        for(int j=0;j<n;j++){                            // 枚举一个点j（0-based）
            if(mask&(1<<j)){                             // 如果j在mask里
                for(int k=j+1;k<n;k++){                  // 枚举另一个点k（k>j避免重复）
                    if(mask&(1<<k)){                     // 如果k也在mask里
                        int rest=mask^(1<<j)^(1<<k);     // 去掉j和k后的剩余集合
                        int edge=(1<<j)|(1<<k);          // j和k组成的两点集合
                        dp[mask]=max(dp[mask],dp[rest]+dp[edge]); // 尝试把(j,k)配成一条边
                    }
                }
                break;                                   // 固定一个j即可（减少重复枚举，提高速度）
            }
        }
    }

    int ALL=(1<<n)-1;                                    // ALL表示所有点都在的集合

    if(n%2==0){                                          // 如果n为偶数
        ans=dp[ALL];                                     // 可以把所有点配完，答案直接是dp[ALL]
    }else{                                               // 如果n为奇数
        ans=0;                                           // 答案初始化为0
        for(int i=0;i<n;i++){                            // 枚举删掉哪个点不参与匹配
            ans=max(ans,dp[ALL^(1<<i)]);                 // 取删掉一个点后的最大匹配
        }
    }

    cout<<ans;                                           // 输出答案
    return 0;                                            // 程序结束
}