Submission #1206730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206730		dksnfjkfnwkfw	Network (BOI15_net)	C++20	18 / 100	2095 ms	17060 KiB

net

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

int n;
vector<pair<int, int>> edges;  // các cạnh ban đầu
vector<pair<int, int>> allPossible;  // các cạnh có thể thêm

bool is_connected_without_edge(vector<vector<int>> &G, pair<int, int> skip_edge) {
    vector<bool> visited(n + 1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) {
            if ((u == skip_edge.first && v == skip_edge.second) || (u == skip_edge.second && v == skip_edge.first)) continue;
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (!visited[i]) return false;
    return true;
}

bool is_good_graph(vector<pair<int, int>> added_edges) {
    vector<vector<int>> G(n + 1);
    for (auto [u, v] : edges) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (auto [u, v] : added_edges) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (auto [u, v] : edges) {
        if (!is_connected_without_edge(G, {u, v})) return false;
    }
    for (auto [u, v] : added_edges) {
        if (!is_connected_without_edge(G, {u, v})) return false;
    }
    return true;
}

int main() {
    cin >> n;
    edges.resize(n - 1);
    set<pair<int, int>> exist;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        exist.insert({min(u, v), max(u, v)});
    }

    // Tạo danh sách các cặp (u, v) có thể thêm
    for (int u = 1; u <= n; ++u) {
        for (int v = u + 1; v <= n; ++v) {
            if (exist.count({u, v}) == 0) {
                allPossible.push_back({u, v});
            }
        }
    }

    // Thử k từ 0 → allPossible.size()
    for (int k = 1; k <= allPossible.size(); ++k) {
        vector<bool> mask(allPossible.size(), false);
        fill(mask.end() - k, mask.end(), true);
        do {
            vector<pair<int, int>> added;
            for (int i = 0; i < allPossible.size(); ++i) {
                if (mask[i]) added.push_back(allPossible[i]);
            }
            if (is_good_graph(added)) {
                cout << k << "\n";
                for (auto [u, v] : added) {
                    cout << u << " " << v << "\n";
                }
                return 0;
            }
        } while (next_permutation(mask.begin(), mask.end()));
    }

    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37