Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout); định dạng xem ở mục Dữ liệu vào.

LeetCode 2039 – The Time When the Network Becomes Idle (Thời điểm mạng trở nên rảnh) – độ khó Medium.

Có một mạng gồm ~n~ máy chủ (server), được đánh số từ ~0~ đến ~n - 1~. Cho mảng số nguyên 2 chiều edges, trong đó edges[i] = [ui, vi] cho biết có một kênh truyền tin giữa hai máy chủ ~u_i~ và ~v_i~, qua kênh này hai máy có thể gửi bao nhiêu tin nhắn cho nhau cũng được, mỗi tin đi trực tiếp mất đúng một giây. Cho thêm mảng số nguyên patience độ dài ~n~ (đánh số từ 0).

Mọi máy chủ đều liên thông, tức là một tin nhắn có thể đi từ một máy chủ bất kỳ tới mọi máy chủ khác, trực tiếp hoặc gián tiếp qua các kênh truyền tin.

Máy chủ số ~0~ là máy chủ chính (master). Các máy còn lại là máy chủ dữ liệu (data). Mỗi máy chủ dữ liệu cần gửi tin nhắn của mình tới máy chủ chính để xử lý và chờ phản hồi. Tin nhắn di chuyển giữa các máy chủ một cách tối ưu, tức là mỗi tin nhắn đi tới máy chủ chính trong thời gian ít nhất. Máy chủ chính xử lý mọi tin nhắn vừa tới ngay lập tức và gửi phản hồi về máy chủ đã gửi tin theo đường đi ngược lại đường mà tin nhắn đã đi.

Tại đầu giây thứ ~0~, mỗi máy chủ dữ liệu gửi tin nhắn của mình đi để được xử lý. Bắt đầu từ giây thứ ~1~, tại đầu mỗi giây, mỗi máy chủ dữ liệu sẽ kiểm tra xem nó đã nhận được phản hồi cho tin nhắn mình gửi chưa (tính cả những phản hồi vừa mới tới):

• Nếu chưa, nó sẽ gửi lại tin nhắn theo chu kỳ. Máy chủ dữ liệu ~i~ sẽ gửi lại tin nhắn mỗi patience[i] giây, tức là máy ~i~ sẽ gửi lại tin nhắn nếu đã trôi qua patience[i] giây kể từ lần gần nhất máy này gửi tin.
• Ngược lại, máy chủ này sẽ không gửi lại nữa.

Mạng được gọi là rảnh (idle) khi không còn tin nhắn nào đang di chuyển giữa các máy chủ hoặc đang tới một máy chủ nào.

Yêu cầu: trả về giây sớm nhất mà bắt đầu từ đó mạng trở nên rảnh.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên ~n~ và ~m~ (~m~ là số phần tử của edges).
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u_i~, ~v_i~ mô tả edges[i].
• Dòng cuối gồm ~n~ số nguyên patience[0], patience[1], ..., patience[n-1].

Kết quả

• In ra một số nguyên là giây sớm nhất mà bắt đầu từ đó mạng trở nên rảnh.

Giới hạn

• n == patience.length
• ~2 \le n \le 10^5~
• patience[0] == 0
• ~1 \le~ patience[i] ~\le 10^5~ với ~1 \le i \lt n~
• ~1 \le m =~ edges.length ~\le \min(10^5, \dfrac{n(n-1)}{2})~
• edges[i].length == 2
• ~0 \le u_i, v_i \lt n~
• ~u_i \ne v_i~
• Không có cạnh lặp.
• Mỗi máy chủ đều có thể tới được mọi máy chủ khác, trực tiếp hoặc gián tiếp.

Sample Input 1

3 2
0 1
1 2
0 2 1

Sample Output 1

8

Giải thích

Tại (đầu) giây 0:

• Máy dữ liệu 1 gửi tin nhắn của nó (ký hiệu 1A) tới máy chủ chính.
• Máy dữ liệu 2 gửi tin nhắn của nó (ký hiệu 2A) tới máy chủ chính.

Tại giây 1:

• Tin 1A tới máy chủ chính. Máy chủ chính xử lý 1A ngay lập tức và gửi phản hồi 1A ngược về.
• Máy 1 chưa nhận được phản hồi nào. Mới trôi qua 1 giây (~1 \lt~ patience[1] ~= 2~) kể từ lần gửi gần nhất, nên nó không gửi lại.
• Máy 2 chưa nhận được phản hồi nào. Đã trôi qua 1 giây (~1 =~ patience[2] ~= 1~) kể từ lần gửi gần nhất, nên nó gửi lại tin nhắn (ký hiệu 2B).

Tại giây 2:

• Phản hồi 1A tới máy 1. Máy 1 sẽ không gửi lại nữa.
• Tin 2A tới máy chủ chính. Máy chủ chính xử lý 2A ngay lập tức và gửi phản hồi 2A ngược về.
• Máy 2 gửi lại tin nhắn (ký hiệu 2C).

...

Tại giây 4:

• Phản hồi 2A tới máy 2. Máy 2 sẽ không gửi lại nữa.

...

Tại giây 7, phản hồi 2D tới máy 2.

Bắt đầu từ đầu giây 8, không còn tin nhắn nào đi giữa các máy chủ hoặc đang tới máy chủ nào. Đây chính là thời điểm mạng trở nên rảnh.

Sample Input 2

3 3
0 1
0 2
1 2
0 10 10

Sample Output 2

3

Giải thích

Máy dữ liệu 1 và 2 nhận được phản hồi cho tin nhắn của mình vào đầu giây 2. Từ đầu giây 3, mạng trở nên rảnh.

Nguồn: LeetCode 2039.