V8ORG spoj – Tổ chức đối lập
Nguồn đề bài: http://vn.spoj.com/problems/V8ORG/ 1. Đề bài V8ORG spoj Ở một đất nước nọ, lực lượng an ninh vừa phát hiện một tổ chức đối lập. Tổ chức đối lập này được tổ chức chặt chẽ, bao gồm mạng lưới thành viên và chỉ huy ở các cấp bậc khác nhau. Các thành viên của tổ chức ...
Nguồn đề bài: http://vn.spoj.com/problems/V8ORG/
1. Đề bài V8ORG spoj
Ở một đất nước nọ, lực lượng an ninh vừa phát hiện một tổ chức đối lập. Tổ chức đối lập này được tổ chức chặt chẽ, bao gồm mạng lưới thành viên và chỉ huy ở các cấp bậc khác nhau. Các thành viên của tổ chức được đánh số từ 1 đến N. Tổ chức có một chỉ huy tối cao, luôn được đánh số 1. Mỗi thành viên chỉ biết viên chỉ huy trực tiếp của mình (có duy nhất một viên chỉ huy trực tiếp) chứ không biết các chỉ huy cấp cao hơn.
Khi tiến hành việc bắt giữ các thành viên, tổ chức sẽ bị phân rã thành các nhóm nhỏ không liên kết với nhau, ví dụ sau khi bắt giữ thành viên số 2 (hình 1), tổ chức bị phân rã thành 4 nhóm. Lực lượng an ninh khẳng định, một nhóm chứa ít hơn K thành viên sẽ không còn là mối đe dọa cho đất nước. Để không làm giảm hình ảnh của đất nước trước dư luận quốc tế, các nhà lãnh đạo an ninh muốn bắt giữ một số lượng ít nhất phần tử đối lập, sao cho các nhóm bị phân rã đều không còn gây nguy hại cho đất nước.
Cho biết cấu trúc của tổ chức đối lập, việc chương trình giúp các nhà lãnh đạo an ninh xác định số lượng phần tử đối lập ít nhất cần bắt giữ.
Dữ liệu
- Dòng đầu tiên chứa số nguyên K (1 ≤ K ≤ 10000).
- Dòng thứ hai chứa số nguyên N (1 ≤ N ≤ 10000).
- Dòng thứ ba chứa N-1 số nguyên cách nhau bởi khoảng trắng, chỉ số của chỉ huy trực tiếp của mỗi phần tử của tổ chức (trừ chỉ huy tối cao): số đầu tiên cho biết chỉ huy của phần tử thứ hai, số thứ hai cho biết chỉ huy của phần tử thứ ba,…
Kết quả
In ra một số nguyên duy nhất là số phần tử đối lập ít nhất cần bắt giữ.
Ví dụ
| Dữ liệu | Kết quả | Mô tả |
|---|---|---|
| 3 14 1 1 2 2 3 2 3 6 6 6 7 4 7  Hình 1 | 4 | Có thể bắt giữ 4 phần tử 6, 2, 7 và 8. |
2. Gợi ý V8ORG spoj
Sử dụng thuật toán DFS.
Bởi vì tổ chức bao gồm mạng lưới thành viên và chỉ huy ở các cấp bậc khác nhau, mỗi thành viên chỉ có duy nhất một viên chỉ huy trực tiếp, và chỉ huy tối cao được đánh số 1. Ta xây dựng một đồ thị vô hướng không có chu trình. Do đó ta DFS từ 1.
Khởi tạo ds=0.
Gọi f[u] là kích thước của cây con gốc u.
Mỗi lần duyệt tới đỉnh u, khỏi tạo f[u]=1. Đỉnh u có con là v, ta sử dụng công thức quy hoạch động để cập nhật f[u]=f[u]+f[v]. Nếu f[u]>=k thì ta gán f[u]=0(cũng tức là cho cây con gốc u có kích thước bằng 0), rồi tăng ds lên 1 đơn vị.
3. Code mẫu V8ORG spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <bits/stdc++.h> using namespace std; int k,n,deg[10001],low[10001],num[10001],cl[10001], pre[10001],f[10001],id=0,ds=0; vector<int> g[10001]; void dfs(int u) { cl[u]=1; num[u]=low[u]=++id; f[u]=1; for(int i=0; i<deg[u]; i++) { int v=g[u][i]; if(cl[v]==0) { pre[v]=u; dfs(v); f[u]+=f[v]; } } if(f[u]>=k) { f[u]=0; ds++; } } int main() { cin>>k>>n; for(int i=2; i<=n; i++) { int a; cin>>a; g[a].push_back(i);deg[a]++; g[i].push_back(a);deg[i]++; } dfs(1); cout<<ds; } |
