Untitled

Bai 5: 
#include <iostream>

using namespace std;

// Hàm kiểm tra xem một nhà hàng có nằm trong phạm vi phục vụ của một điểm solitaire không
bool isCovered(int restaurantX, int restaurantY, int solitaireX, int solitaireY, int radius) {
    return ((restaurantX - solitaireX) * (restaurantX - solitaireX) + (restaurantY - solitaireY) * (restaurantY - solitaireY)) <= (radius * radius);
}

// Hàm tính tổng số người được phục vụ bởi các nhà hàng trong một tổ hợp nhất định của các nhà hàng
int calculateTotalCoverage(int chosenRestaurantsX[], int chosenRestaurantsY[], int solitairesX[], int solitairesY[], int solitairePeople[], int R, int K, int M, int N) {
    int totalCoverage = 0;
    for (int solitaireIndex = 0; solitaireIndex < N; ++solitaireIndex) {
        for (int restaurantIndex = 0; restaurantIndex < M; ++restaurantIndex) {
            if (isCovered(chosenRestaurantsX[restaurantIndex], chosenRestaurantsY[restaurantIndex], solitairesX[solitaireIndex], solitairesY[solitaireIndex], R)) {
                totalCoverage += solitairePeople[solitaireIndex];
                break; // Chỉ tính một solitaire một lần (được phục vụ bởi nhà hàng đầu tiên)
            }
        }
    }
    return totalCoverage;
}

// Hàm đệ quy để sinh ra tất cả các tổ hợp chập K của M
void generateCombinations(int arr[], int data[], int start, int end, int index, int K, int M, int N, int& maxTotalCoverage, int restaurantsX[], int restaurantsY[], int solitairesX[], int solitairesY[], int solitairePeople[], int R) {
    // Nếu đã chọn đủ K phần tử, xử lý tổ hợp này
    if (index == K) {
        int totalCoverage = calculateTotalCoverage(data, restaurantsY, solitairesX, solitairesY, solitairePeople, R, K, M, N);
        maxTotalCoverage = max(maxTotalCoverage, totalCoverage);
        return;
    }

    // Duyệt qua các phần tử để chọn
    for (int i = start; i <= end && end - i + 1 >= K - index; ++i) {
        data[index] = arr[i]; // Chọn một phần tử
        // Đệ quy để chọn các phần tử tiếp theo
        generateCombinations(arr, data, i + 1, end, index + 1, K, M, N, maxTotalCoverage, restaurantsX, restaurantsY, solitairesX, solitairesY, solitairePeople, R);
    }
}

int main() {
    int K, R, M, N;

    cin >> K >> R >> M; // Nhập số lượng nhà hàng, bán kính phục vụ và số lượng nhà hàng

    int restaurantsX[M], restaurantsY[M];
    // Nhập tọa độ của các nhà hàng
    for (int i = 0; i < M; ++i) {
        cin >> restaurantsX[i] >> restaurantsY[i];
    }

    cin >> N; // Nhập số lượng điểm solitaire

    int solitairesX[N], solitairesY[N], solitairePeople[N];
    // Nhập tọa độ và số lượng người của các điểm solitaire
    for (int i = 0; i < N; ++i) {
        cin >> solitairesX[i] >> solitairesY[i] >> solitairePeople[i];
    }

    int maxTotalCoverage = 0;

    // Sinh tất cả các tổ hợp chập K của M
    int data[K];
    generateCombinations(restaurantsX, data, 0, M - 1, 0, K, M, N, maxTotalCoverage, restaurantsX, restaurantsY, solitairesX, solitairesY, solitairePeople, R);

    // In ra tổng số người lớn nhất có thể phục vụ được
    cout << maxTotalCoverage << endl;

    return 0;
}
bai 4: 
Đọc đầu vào:

Đọc số lượng bộ test (num_testcases) từ dòng đầu tiên.
Lặp qua từng bộ test:
Đọc số lượng đảo (num_islands) từ dòng đầu tiên.
Đọc ma trận kề của đồ thị lưới điện, mỗi dòng đại diện cho một đảo và mỗi phần tử trong ma trận biểu thị sự tồn tại của đường dây điện giữa hai đảo tương ứng (1) hoặc không (0).
2. Tìm số lượng thành phần liên thông:

Sử dụng thuật toán duyệt sâu (DFS) để tìm số lượng thành phần liên thông cho mỗi đảo.
Hàm dfs được gọi cho mỗi đảo, đánh dấu các đảo đã truy cập và đếm số lượng nút trong thành phần liên thông.
Kết quả được lưu trữ trong mảng num_connected_components, với vị trí tương ứng với số lượng thành phần liên thông của đảo tương ứng.
3. Tìm đảo cần phá hủy:

Khởi tạo hai biến: max_components để lưu trữ số lượng thành phần liên thông tối đa sau khi phá hủy một đảo và island_to_destroy để lưu trữ chỉ số của đảo cần phá hủy.
Lặp qua từng đảo:
Tính toán số lượng thành phần liên thông sẽ còn lại sau khi phá hủy đảo hiện tại bằng cách cộng số lượng thành phần liên thông của tất cả các đảo láng giềng với đảo hiện tại.
Nếu số lượng thành phần liên thông sau khi phá hủy lớn hơn max_components, cập nhật max_components và island_to_destroy.
Sau khi lặp qua tất cả các đảo, island_to_destroy sẽ là chỉ số của đảo cần phá hủy để chia cắt hệ thống điện thành nhiều phần nhất.
4. Xuất kết quả:
#include <iostream> 

using namespace std; 

// Hàm đệ quy DFS (Duyệt sâu) để tìm số lượng đảo liên thông
void dfs(int island, int graph[][100], bool visited[], int& count, int num_islands) {
    if (visited[island]) {
        return; // Nếu đảo đã được thăm, không làm gì cả
    }

    visited[island] = true; // Đánh dấu đảo hiện tại đã được thăm
    count++; // Tăng biến đếm thành phần liên thông

    // Duyệt qua tất cả các đảo láng giềng của đảo hiện tại
    for (int neighbor = 0; neighbor < num_islands; neighbor++) {
        // Nếu có đường nối giữa đảo hiện tại và đảo láng giềng và đảo láng giềng chưa được thăm
        if (graph[island][neighbor] == 1 && !visited[neighbor]) {
            dfs(neighbor, graph, visited, count, num_islands); // Tiến hành duyệt sâu từ đảo láng giềng
        }
    }
}

int main() {
    int num_testcases;
    cin >> num_testcases; // Nhập số lượng bộ test

    // Duyệt qua từng bộ test
    for (int testcase = 1; testcase <= num_testcases; testcase++) {
        int num_islands;
        cin >> num_islands; // Nhập số lượng đảo

        // Khởi tạo ma trận kề của đồ thị lưới điện
        int graph[100][100];

        // Nhập ma trận kề từ đầu vào
        for (int i = 0; i < num_islands; i++) {
            for (int j = 0; j < num_islands; j++) {
                cin >> graph[i][j];
            }
        }

        // Khởi tạo mảng visited để đánh dấu các đảo đã được thăm
        bool visited[100] = {false};

        // Tính số lượng thành phần liên thông của mỗi đảo
        int num_connected_components[100] = {0};
        for (int island = 0; island < num_islands; island++) {
            int count = 0; // Biến đếm số lượng đảo liên thông
            dfs(island, graph, visited, count, num_islands); // Gọi hàm DFS
            num_connected_components[island] = count; // Lưu số lượng thành phần liên thông của đảo hiện tại
            fill_n(visited, num_islands, false); // Đặt lại mảng visited để chuẩn bị cho lần duyệt tiếp theo
        }

        // Tìm đảo cần phá hủy để chia cắt hệ thống điện thành nhiều phần nhất
        int max_components = 0;
        int island_to_destroy = -1;
        for (int island = 0; island < num_islands; island++) {
            int components_after_removal = 0; // Số lượng thành phần liên thông sau khi phá hủy đảo
            for (int other_island = 0; other_island < num_islands; other_island++) {
                // Nếu có đường nối giữa đảo cần phá hủy và đảo khác, cộng số lượng thành phần liên thông của đảo khác vào
                if (graph[island][other_island] == 1) {
                    components_after_removal += num_connected_components[other_island];
                }
            }
            // So sánh và cập nhật nếu tìm thấy đảo có thể tạo ra nhiều thành phần liên thông nhất
            if (components_after_removal > max_components) {
                max_components = components_after_removal;
                island_to_destroy = island;
            }
        }

        // In ra kết quả
        if (max_components == 0) {
            cout << 0 << endl; // Nếu không thể chia cắt được hệ thống điện, xuất ra 0
        } else {
            cout << island_to_destroy + 1 << endl; // In ra đảo cần phá hủy (index bắt đầu từ 0)
        }
    }

    return 0;
}