Bài toán Mời khách dự tiệc

Mời khách dự tiệc

Bài toán – Mời khách dự tiệc

Công ty trách nhiệm hữu hạn “Vui vẻ” có n cán bộ đánh số từ 1 đến n. Cán bộ i có đánh giá độ vui tính là vi (i = 1, 2, …, n). Ngoại trừ Giám đốc Công ty, mỗi cán bộ có 1 thủ trưởng trực tiếp của mình.

Bạn chỉ cần giúp Công ty mời một nhóm cán bộ đến dự dạ tiệc “Vui vẻ” sao cho trong số những người được mời không đồng thời có mặt nhân viên và thủ trưởng trực tiếp và đồng thời tổng đánh giá độ vui tính của những người dự tiệc là lớn nhất.

Giả thiết rằng mỗi một thủ trưởng có không quá 20 cán bộ trực tiếp dưới quyền.

 Dữ liệu: Vào từ file văn bản GUEST.INP

– Dòng đầu tiên ghi số cán bộ của Công ty: n (1 < n < 1001);

– Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên dương ti, vi; trong đó ti là số hiệu của thủ trưởng trực tiếp và vi là độ vui tính của cán bộ i (i = 1, 2, …, n). Quy ước ti = 0 nếu i là số hiệu của Giám đốc Công ty.

Kết quả: Ghi ra file văn bản GUEST.OUT

– Dòng đầu tiên ghi hai số m, v; trong đó m là tổng số cán bộ được mời còn v là tổng độ vui tính của các cán bộ được mời dự tiệc;

– Dòng thứ i trong số m dòng tiếp theo ghi số hiệu của cán bộ được mời thứ i (i = 1, 2, …, m).

Ví dụ:

GUEST.INP

GUEST.OUT

3

0 3

1 6

2 4

2 7

1

3

 

 

GUEST.INP

GUEST.OUT

7

0 1

1 1

1 12

2 50

2 1

3 1

3 1

3 63

3

4

5

 

Thuật toán

Để giải bài toán này, ta có thể sử dụng thuật toán tham lam (greedy algorithm) bằng cách sắp xếp các cán bộ theo độ vui tính giảm dần. Sau đó, ta bắt đầu lần lượt thêm các cán bộ vào danh sách khách mời, nhưng chỉ thêm những cán bộ không có thủ trưởng trực tiếp và cán bộ có thủ trưởng trực tiếp chưa được mời trước đó.

Để kiểm tra xem một cán bộ có thể được mời hay không, ta cần kiểm tra xem thủ trưởng của cán bộ đó đã được mời hay chưa. Nếu thủ trưởng đã được mời, thì cán bộ đó không được mời.

Sau khi đã chọn được danh sách khách mời, ta chỉ cần tính tổng số cán bộ và tổng độ vui tính của họ.

Độ phức tạp của thuật toán này là O(n log n) do ta cần sắp xếp các cán bộ theo độ vui tính giảm dần.

Cài đặt bài toán với Python

# Đọc dữ liệu vào từ file
with open("GUEST.INP", "r") as f:
    n = int(f.readline())
    guest_data = [list(map(int, line.split())) for line in f.readlines()]

# Sắp xếp các cán bộ theo độ vui tính giảm dần
guest_data.sort(key=lambda x: x[1], reverse=True)

# Khởi tạo danh sách khách mời
guests = []
invited_managers = set()

# Thêm các cán bộ vào danh sách khách mời
for data in guest_data:
    if data[0] == 0 or data[0] not in invited_managers:
        guests.append(data)
        if data[0] != 0:
            invited_managers.add(data[0])

# Tính tổng số cán bộ và tổng độ vui tính của các khách mời
total_guests = len(guests)
total_happiness = sum(data[1] for data in guests)

# Ghi kết quả ra file
with open("GUEST.OUT", "w") as f:
    f.write("{} {}\n".format(total_guests, total_happiness))
    for data in guests:
        f.write("{}\n".format(data[0]))

Cài đặt bài toán với C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

const int MAXN = 1001;

int n, ti[MAXN], vi[MAXN];
vector<int> adj[MAXN], res;

void input() {
    ifstream fin("GUEST.INP");
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        int t;
        fin >> t >> vi[i];
        if (t != 0) {
            adj[t].push_back(i);
        }
    }
    fin.close();
}

void dfs(int u, int p, int &m, int &v, vector<int> &temp) {
    temp.push_back(u);
    m++;
    v += vi[u];
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u, m, v, temp);
        }
    }
}

void solve() {
    for (int i = 1; i <= n; ++i) {
        if (ti[i] == 0) {
            int m = 0, v = 0;
            vector<int> temp;
            dfs(i, 0, m, v, temp);
            if (m <= 20) {
                res = max(res, temp, [&](int x, int y) { return vi[x] < vi[y]; });
            }
        }
    }
}

void output() {
    ofstream fout("GUEST.OUT");
    fout << res.size() << " " << accumulate(res.begin(), res.end(), 0, [&](int s, int u) { return s + vi[u]; }) << endl;
    for (int u : res) {
        fout << u << endl;
    }
    fout.close();
}

int main() {
    input();
    solve();
    output();
    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *