SPOJ.COM – Thuật toán bài GCPC11J - Time to live

05/12/2016 7 minutes read
Share:

Đề bài:

Như bạn đã biết, hầu hết mạng máy tính được tổ chức dạng cây, tức là mỗi máy tính sẽ có thể kết nối với một và chỉ một máy tính khác. Có một khái niệm đó là Time to Live (TTL) được xác định là sau bao nhiêu bước một gói tin trong mạng bị mất nếu như nó không thể tới đúng đích. Mục đích của TTL là để tránh trường hợp gói tin lan truyền vòng tròn trong mạng dẫn đến lỗi.

Điểm đặt của bộ định tuyến (router) cái kết nối mạng với mạng khác là tối ưu khi mà giá trị lớn nhất cần có của TTL để gói tin được gửi từ router này sang bất kì router khác trong cùng một mạng là nhỏ nhất.

Cho trước thông tin của mạng. Bạn hãy tính giá trị lớn nhất cần phải có của TTL ở mạng này nếu như bạn có thể chọn một máy tính làm vai trò của router.

Đầu vào:

Dòng đầu tiên của đầu vào bao gồm số c, với 1 ≤ c ≤ 100, là số lượng test case. Mỗi test case bắt đầu với một dòng chứa số N, là số lượng máy tính trong mạng 1 < N ≤ 105. Máy tính được đánh số từ 0 đến N - 1. Sau đó là N - 1 dòng, xác định kết nối giữa 2 máy tính, gồm 2 số a và b. Có nghĩa là máy tính a kết nối với máy tính b và ngược lại, 0 ≤ a,b < N.

Đầu ra:

Với mỗi test case, in ra một dòng chứa giá trị tối ưu nhất của TTL.

Ví dụ:

Đầu vào:

3
2
1 0
5
3 2
2 1
0 2
2 4
9
3 1
6 5
3 4
0 3
8 1
1 7
1 6
2 3

Đầu ra:

1
1
2

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/GCPC11J/

Phân tích:

  • Bài này thực chất là tôi phải đi tìm khoảng cách lớn nhất của 2 điểm trên cây. Tôi sẽ sử dụng 2 lần thuật toán tìm kiếm theo chiều rộng BFS để tìm ra khoảng cách này. Lần thứ nhất tôi bắt đầu từ điểm bất kì và tìm ra điểm xa nhất so với điểm bắt đầu này. Sau khi tìm được điểm xa nhất trong lần thứ nhất, tôi sẽ tiếp tục áp dụng BFS lần thứ 2 từ điểm vừa mới tìm được. Và tôi lại tìm được điểm xa nhất so với điểm bắt đầu lần thứ 2. Lúc này tôi tìm được khoảng cách xa nhất giữa 2 điểm trên cây. Giả sử là x.

  • Lúc này, nếu x chẵn thì giá trị TTL = x / 2. Còn nếu x lẻ thì TTL = x / 2 + 1.

  • Một điểm chú ý ở đây là số điểm N khá lớn. Do đó tôi sẽ sử dụng danh sách liên kết để xác định liên kết giữa các điểm.

Lời giải:

(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)

Code C/C++:

#include <iostream>
using namespace std;
const int MAX = 100005;
typedef struct Node
{
int id;
Node *next;
}Node;
class List
{
public:
Node *begin;
public:
List()
{
begin = 0;
}
void Add(int id)
{
Node *tmp = new Node;
tmp->id = id;
tmp->next = begin;
begin = tmp;
}
int GetLength()
{
int cnt = 0;
Node *p = begin;
while (p!=0)
{
cnt++;
p = p->next;
}
return cnt;
}
};
int N, Answer, IdMax;
List MyList[MAX];
int Mark[MAX];
int queue[MAX];
int fr, re, leng;
void EnQueue(int id)
{
queue[re] = id;
re = (re + 1) % MAX;
leng++;
}
int DeQueue()
{
int p = queue[fr];
fr = (fr + 1) % MAX;
leng--;
return p;
}
void BFS(int u)
{
for(int i = 0; i < N; i++)
Mark[i] = 0;
fr = re = leng = 0;
EnQueue(u);
Mark[u] = 1;
while(leng > 0)
{
int v = DeQueue();
Node *p = MyList[v].begin;
while(p != 0)
{
int k = p->id;
if(!Mark[k])
{
Mark[k] = Mark[v] + 1;
if(Mark[k] > Answer)
{
IdMax = k;
Answer = Mark[k];
}
EnQueue(k);
}
p = p->next;
}
}
}
int main()
{
ios::sync_with_stdio(false);
// freopen("input.txt","r",stdin);
int T;
cin >> T;
for(int tc = 0; tc < T; tc++)
{
IdMax = Answer = 0;
cin >> N;
for(int i = 0; i < N; i++)
MyList[i].begin = 0;
int a,b;
for(int i = 0; i < N-1; i++)
{
cin >> a >> b;
MyList[a].Add(b);
MyList[b].Add(a);
}
BFS(1);
BFS(IdMax);
Answer--;
if(Answer%2==0) Answer /= 2;
else Answer = Answer / 2 + 1;
cout << Answer << endl;
}
return 0;
}
view raw GCPC11J.cpp hosted with ❤ by GitHub

Code by Phạm Văn Lâm.

Share: