用c++代码计算一个向量组成的矩阵中的极小碰集

以下是一个简单的 C++ 代码，用于计算由向量组成的矩阵中的极小碰集（minimal hitting set）。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> minimal_hitting_set(vector<vector<int>> matrix) {
    vector<int> hitting_set;
    int n = matrix.size();
    vector<int> indices(n);
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    while (!matrix.empty()) {
        int max_count = 0;
        int max_index = -1;
        for (int i = 0; i < matrix[0].size(); i++) {
            int count = 0;
            int index = -1;
            for (int j = 0; j < matrix.size(); j++) {
                if (matrix[j][i] == 1) {
                    count++;
                    index = j;
                }
            }
            if (count > max_count) {
                max_count = count;
                max_index = index;
            }
        }
        hitting_set.push_back(indices[max_index]);
        vector<vector<int>> new_matrix;
        for (int i = 0; i < matrix.size(); i++) {
            if (matrix[i][max_index] == 0) {
                new_matrix.push_back(matrix[i]);
                indices.erase(indices.begin() + i);
            }
        }
        matrix = new_matrix;
    }
    return hitting_set;
}

int main() {
    vector<vector<int>> matrix = {{1, 0, 1, 0},
                                  {1, 1, 0, 1},
                                  {0, 1, 0, 1},
                                  {1, 1, 1, 0}};
    vector<int> hitting_set = minimal_hitting_set(matrix);
    cout << "Minimal Hitting Set: {";
    for (int i = 0; i < hitting_set.size(); i++) {
        cout << hitting_set[i];
        if (i != hitting_set.size() - 1) {
            cout << ", ";
        }
    }
    cout << "}" << endl;
    return 0;
}

该代码使用了贪心算法来计算极小碰集。首先，将所有向量的索引保存在一个向量 `indices` 中。然后，对于每个向量中的每个元素，计算出包含该元素的向量数量，并将具有最大数量的向量所在的行的索引存储在 `max_index` 中。接下来，将该索引添加到 `hitting_set` 中，并删除包含该索引的行和相应的索引。重复这个过程，直到矩阵为空。

在上面的示例中，我们使用输入矩阵计算最小碰集，并将结果输出到控制台。该矩阵的行表示不同的集合，而列表示元素。如果一个元素在一个集合中，那么矩阵中对应的值为1，否则为0。