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

Đề 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 ≤ 10⁵. 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

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à mình phải đi tìm khoảng cách lớn nhất của 2 điểm trên cây. Mình 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 mình 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, mình sẽ tiếp tục áp dụng BFS lần thứ 2 từ điểm vừa mới tìm được. Và mình 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 mình 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 đó mình 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

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 mình 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 mình 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 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;
}