lessons/参考实现/12-历年真题/洛谷-P15653.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

// Standalone local-protocol version.  The official submission keeps solve_case
// and replaces the final verifier by calls to report() and invert().

struct Result {
    int maximum_edges = 0;
    std::vector<std::vector<int>> operations;
};

namespace {
using Matrix = std::vector<std::vector<unsigned char>>;

void toggle_clique(Matrix& difference, const std::vector<int>& vertices) {
    for (std::size_t i = 0; i < vertices.size(); ++i) {
        for (std::size_t j = i + 1; j < vertices.size(); ++j) {
            int u = vertices[i];
            int v = vertices[j];
            difference[u][v] ^= 1;
            difference[v][u] ^= 1;
        }
    }
}

void add_operation(Matrix& difference, std::vector<std::vector<int>>& operations,
                   std::vector<int> vertices) {
    toggle_clique(difference, vertices);
    for (int& vertex : vertices) ++vertex;  // local matrix is zero-indexed
    operations.push_back(std::move(vertices));
}

Matrix make_best_target(const Matrix& initial, int k, int& maximum_edges) {
    int n = static_cast<int>(initial.size());
    int complete_edges = n * (n - 1) / 2;
    int edge_count = 0;
    std::vector<int> degree_parity(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            if (initial[u][v]) {
                ++edge_count;
                degree_parity[u] ^= 1;
                degree_parity[v] ^= 1;
            }
        }
    }

    Matrix missing(n, std::vector<unsigned char>(n, 0));
    auto add_missing = [&](int u, int v) {
        missing[u][v] = missing[v][u] = 1;
    };

    int residue = k % 4;
    if (residue == 0) {
        if (((complete_edges - edge_count) & 1) != 0) add_missing(0, 1);
    } else if (residue == 1 || residue == 3) {
        std::vector<int> odd;
        for (int vertex = 0; vertex < n; ++vertex) {
            int required_missing_parity = ((n - 1) & 1) ^ degree_parity[vertex];
            if (required_missing_parity) odd.push_back(vertex);
        }
        for (std::size_t i = 0; i < odd.size(); i += 2)
            add_missing(odd[i], odd[i + 1]);

        if (residue == 1) {
            int required_edge_parity = (complete_edges - edge_count) & 1;
            int current_missing = static_cast<int>(odd.size() / 2);
            if ((current_missing & 1) != required_edge_parity) {
                if (odd.empty()) {
                    add_missing(0, 1);
                    add_missing(1, 2);
                    add_missing(2, 0);
                } else {
                    int first = odd[0];
                    int second = odd[1];
                    int middle = 0;
                    while (middle == first || middle == second) ++middle;
                    missing[first][second] = missing[second][first] = 0;
                    add_missing(first, middle);
                    add_missing(middle, second);
                }
            }
        }
    }

    Matrix target(n, std::vector<unsigned char>(n, 0));
    int missing_count = 0;
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            target[u][v] = target[v][u] = missing[u][v] ^ 1;
            missing_count += missing[u][v];
        }
    }
    maximum_edges = complete_edges - missing_count;
    return target;
}

bool finish_k_plus_two(Matrix& difference, const std::vector<int>& remaining,
                       std::vector<std::vector<int>>& operations) {
    int h = static_cast<int>(remaining.size());
    std::vector<int> degree(h, 0);
    for (int i = 0; i < h; ++i)
        for (int j = i + 1; j < h; ++j)
            if (difference[remaining[i]][remaining[j]]) degree[i] ^= 1, degree[j] ^= 1;

    for (int total_parity = 0; total_parity < 2; ++total_parity) {
        std::vector<int> incident_parity(h, 0);
        bool possible = true;
        if ((h & 1) == 0) {
            for (int i = 0; i < h; ++i)
                incident_parity[i] = degree[i] ^ total_parity;
        } else {
            for (int value : degree) possible = possible && value == 0;
        }
        if (!possible) continue;

        std::vector<std::pair<int, int>> selected;
        int actual_total = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = i + 1; j < h; ++j) {
                int use = difference[remaining[i]][remaining[j]] ^ total_parity ^
                          incident_parity[i] ^ incident_parity[j];
                if (use) selected.push_back({i, j}), actual_total ^= 1;
            }
        }
        if (actual_total != total_parity) continue;

        Matrix trial = difference;
        for (auto [left_out, right_out] : selected) {
            std::vector<int> clique;
            for (int i = 0; i < h; ++i)
                if (i != left_out && i != right_out) clique.push_back(remaining[i]);
            toggle_clique(trial, clique);
        }
        bool zero = true;
        for (int i = 0; i < h; ++i)
            for (int j = i + 1; j < h; ++j)
                zero = zero && trial[remaining[i]][remaining[j]] == 0;
        if (!zero) continue;

        for (auto [left_out, right_out] : selected) {
            std::vector<int> clique;
            for (int i = 0; i < h; ++i)
                if (i != left_out && i != right_out) clique.push_back(remaining[i]);
            add_operation(difference, operations, std::move(clique));
        }
        return true;
    }
    return false;
}

Result solve_case(const Matrix& initial, int k) {
    int n = static_cast<int>(initial.size());
    Result result;
    Matrix target = make_best_target(initial, k, result.maximum_edges);
    Matrix difference = initial;
    for (int u = 0; u < n; ++u)
        for (int v = u + 1; v < n; ++v)
            difference[u][v] = difference[v][u] = initial[u][v] ^ target[u][v];

    std::vector<int> remaining(n);
    std::iota(remaining.begin(), remaining.end(), 0);
    const int subset_size = k - 1;
    while (static_cast<int>(remaining.size()) > k + 2) {
        int vertex = remaining.back();
        remaining.pop_back();
        std::vector<int> universe = remaining;
        std::vector<int> base(universe.begin(), universe.begin() + subset_size);
        std::vector<int> outside(universe.begin() + subset_size, universe.end());
        int base_zero = base[0];
        int outside_zero = outside[0];

        int outside_other_xor = 0;
        for (std::size_t i = 1; i < outside.size(); ++i)
            outside_other_xor ^= difference[vertex][outside[i]];
        int base_rest_xor = 0;
        for (int i = 1; i < subset_size; ++i)
            base_rest_xor ^= difference[vertex][base[i]];

        int total_coefficient = 0;
        if (subset_size & 1) {
            int a_zero = difference[vertex][outside_zero] ^ base_rest_xor;
            int all_a = a_zero ^ outside_other_xor;
            total_coefficient = difference[vertex][base_zero] ^ all_a;
        }

        std::vector<int> a(outside.size(), 0);
        std::vector<int> c(subset_size, 0);
        for (std::size_t i = 1; i < outside.size(); ++i)
            a[i] = difference[vertex][outside[i]];
        int all_c = ((subset_size - 1) & 1) * total_coefficient ^ base_rest_xor;
        a[0] = difference[vertex][outside_zero] ^ all_c;
        for (int i = 1; i < subset_size; ++i)
            c[i] = total_coefficient ^ difference[vertex][base[i]];
        int all_a = 0;
        for (int value : a) all_a ^= value;
        int base_coefficient = total_coefficient ^ all_a ^ all_c;

        if (base_coefficient) {
            std::vector<int> clique = base;
            clique.push_back(vertex);
            add_operation(difference, result.operations, std::move(clique));
        }
        for (std::size_t i = 0; i < outside.size(); ++i) {
            if (!a[i]) continue;
            std::vector<int> clique = base;
            clique[0] = outside[i];
            clique.push_back(vertex);
            add_operation(difference, result.operations, std::move(clique));
        }
        for (int i = 1; i < subset_size; ++i) {
            if (!c[i]) continue;
            std::vector<int> clique = base;
            clique[i] = outside_zero;
            clique.push_back(vertex);
            add_operation(difference, result.operations, std::move(clique));
        }
    }

    if (!finish_k_plus_two(difference, remaining, result.operations)) {
        result.maximum_edges = -1;  // This can only indicate a construction bug.
    }
    return result;
}
}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test_point, test_cases;
    std::cin >> test_point >> test_cases;
    (void)test_point;
    while (test_cases--) {
        int n, m, k, operation_limit;
        std::cin >> n >> m >> k >> operation_limit;
        Matrix graph(n, std::vector<unsigned char>(n, 0));
        for (int i = 0; i < m; ++i) {
            int u, v;
            std::cin >> u >> v;
            --u;
            --v;
            graph[u][v] = graph[v][u] = 1;
        }

        Result result = solve_case(graph, k);
        bool valid = result.maximum_edges >= 0 &&
                     static_cast<int>(result.operations.size()) <= operation_limit;
        for (const auto& operation : result.operations) {
            valid = valid && static_cast<int>(operation.size()) == k;
            std::vector<int> zero_indexed = operation;
            for (int& vertex : zero_indexed) --vertex;
            toggle_clique(graph, zero_indexed);
        }
        int final_edges = 0;
        for (int u = 0; u < n; ++u)
            for (int v = u + 1; v < n; ++v) final_edges += graph[u][v];
        valid = valid && final_edges == result.maximum_edges;
        std::cout << result.maximum_edges << ' ' << (valid ? 1 : 0) << '\n';
    }
    return 0;
}