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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {

    // 建图
    void buildGraph(vector<vector<int>>& edges, vector<int>& nums, int numSlots) {
        int n = nums.size();
        edges = vector<vector<int>>(n,vector<int>(2*numSlots));
        for(int i=0; i<n; i++) {
            for(int j=0; j<numSlots; j++) {
                edges[i][j] = edges[i][j+numSlots] = (nums[i]&(j+1));   // j，j+numSlots 分别表示编号为 j+1 的篮子的两个空位
            }
        }
    }

    // KM算法寻找最大权匹配
    // 在匈牙利算法的基础上增加期望度机制。
        // 初始化左半图每个number的期望度为该number最大可获得权值，右半图每个slot的期望度为0。
        // 每次匹配时，只考虑边权等于相连number和slot期望度和的边。
        // 当一次匹配中无法成功时，执行期望度更新操作：将涉及的所有number期望度减一、所有slot期望度加一。
    int KM(vector<vector<int>>& edges) {
        int n = edges.size(), m = edges[0].size();  // 二分图两边的点数
        vector<int> match(m, -1); // match[i]为teacher[i]匹配的student编号
        vector<int> exNumber(n); // number期望
        vector<int> exSlot(m, 0); // slot的期望
        for (int i = 0; i < n; ++i) {
            exNumber[i] = *max_element(edges[i].begin(), edges[i].end());
        }
        // 为每个number匹配teacher
        for (int i = 0; i < n; ++i) {
            while(true) {
                vector<bool> visNumber(n, false);
                vector<bool> visSlot(m, false);
                if (dfs(i, m, edges, match, visNumber, visSlot, exNumber, exSlot)) break;
                // 无法匹配降低期望
                for (int j = 0; j < n; ++j) {
                    if (visNumber[j]) exNumber[j]--;
                }
                for (int j = 0; j < m; ++j) {
                    if (visSlot[j]) exSlot[j]++;
                }
            }
        }

        int ans = 0;
				// 将每一对匹配的权值加和（这里通过遍历slot的匹配情况来实现）
        for (int i = 0; i < m; ++i) if(match[i]!=-1) {
            ans += edges[match[i]][i];
        }
        return ans;
    }

    // 匈牙利算法寻找完美匹配
    // 为第i个number寻找匹配的slot。对每个可匹配slot，若已被其他number匹配，则递归为其他number寻找另外的可匹配slot；找不到则为该number匹配其他slot
    bool dfs(int i, int m, vector<vector<int>>& edges, vector<int>& match, vector<bool>& visNumber, vector<bool>& visSlot, vector<int>& exNumber, vector<int>& exSlot) {
        visNumber[i] = true;
        for (int j = 0; j < m; ++j) {
            if (visSlot[j]) continue;
            int diff = exNumber[i] + exSlot[j] - edges[i][j];
            if (!diff) {
                visSlot[j] = true;
                if (match[j] == -1 || dfs(match[j], m, edges, match, visNumber, visSlot, exNumber, exSlot)) {
                    match[j] = i;
                    return true;
                }
            }
        }
        return false;
    }
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        /* 
         * 问题抽象为 “n个数字 - 2*numSlots个篮子” 的二分图最大匹配问题
         ** 二分图中的点：
         *** n个数字：nums中需要被分配的n个数字
         *** 2*numSlots个篮子：每个篮子最多可以放两个数字
         ** 二分图中的边：
         *** 每个数字和每个篮子间都有一条边，边权为数字与篮子编号的 按位与运算 结果，表示把该数字放到该篮子时可获得的权值
         */
        
        // 建图（用n*2numSlots的邻接矩阵表示图。因为后续算法中只需要考虑边权而不需要考虑点权，故只需保存边权信息。）
        vector<vector<int>> edges;
        buildGraph(edges,nums,numSlots);
        // 计算（使用KM算法，计算最优匹配方案权值和）
        return KM(edges);
    }
};