验证集可达到的最优F1值

#include <iostream>
#include <vector>
#include <unordered_set>
#include <iomanip>

using namespace std;

struct Node {
    int l, r;     // 左右子节点编号（0表示无子节点）
    int f, th;    // 分裂特征（1-based）、阈值；叶子节点时f和th为0
    int label;    // 叶子节点的输出标签（0或1）
};

Node nodes[105];  // 节点编号1~N，最多100个节点

// 预测单个样本的标签（基于当前剪枝方案）
int predict(int node_idx, const unordered_set<int>& pruned, const vector<int>& sample) {
    if (pruned.count(node_idx)) {  // 节点被剪枝，直接返回其label
        return nodes[node_idx].label;
    }
    if (nodes[node_idx].l == 0 && nodes[node_idx].r == 0) {  // 叶子节点，直接返回label
        return nodes[node_idx].label;
    }
    // 非叶子且未剪枝，按分裂规则遍历子节点
    int f = nodes[node_idx].f;
    int th = nodes[node_idx].th;
    if (sample[f - 1] <= th) {  // 特征是1-based，样本存储是0-based
        return predict(nodes[node_idx].l, pruned, sample);
    } else {
        return predict(nodes[node_idx].r, pruned, sample);
    }
}

// 计算当前剪枝方案下的F1值
double calculateF1(const unordered_set<int>& pruned, const vector<vector<int>>& samples) {
    int TP = 0, FP = 0, FN = 0;
    for (const auto& sample : samples) {
        int pred = predict(1, pruned, sample);  // 从根节点（编号1）开始预测
        int true_label = sample.back();         // 真实标签在样本最后一位
        if (pred == 1 && true_label == 1) {
            TP++;
        } else if (pred == 1 && true_label == 0) {
            FP++;
        } else if (pred == 0 && true_label == 1) {
            FN++;
        }
        // pred==0且true_label==0时，不影响TP、FP、FN
    }
    if (TP == 0) {  // 无真正例时F1为0
        return 0.0;
    }
    return 2.0 * TP / (2.0 * TP + FP + FN);
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 1; i <= N; ++i) {
        cin >> nodes[i].l >> nodes[i].r >> nodes[i].f >> nodes[i].th >> nodes[i].label;
    }

    vector<vector<int>> samples(M, vector<int>(K + 1));
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j <= K; ++j) {
            cin >> samples[i][j];
        }
    }

    // 筛选内部节点（左右子节点均存在的节点）
    vector<int> internal_nodes;
    for (int i = 1; i <= N; ++i) {
        if (nodes[i].l != 0 && nodes[i].r != 0) {
            internal_nodes.push_back(i);
        }
    }

    int m = internal_nodes.size();
    double max_f1 = 0.0;

    // 枚举所有剪枝组合（位掩码法，共2^m种可能）
    for (int mask = 0; mask < (1 << m); ++mask) {
        unordered_set<int> pruned;  // 记录当前剪枝的节点
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                pruned.insert(internal_nodes[i]);
            }
        }
        // 计算当前剪枝方案的F1值
        double current_f1 = calculateF1(pruned, samples);
        if (current_f1 > max_f1) {
            max_f1 = current_f1;
        }
    }

    cout << fixed << setprecision(6) << max_f1 << endl;

    return 0;
}