Archives for Tháng Mười Hai 2017

Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”,
nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching”
không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài
ra đây cũng là một nội dung được đề cập trong TAoCP – Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link).
Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP – Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được
độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng
vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay
shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không
thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ
lưu trữ ngoại vi trở nên tốn kém ( link ).
Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc
dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời
mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần
References. Một phiên bản cải tiến với kích thức mảng $N$ bất
kì sẽ được update sau.

[[code]]czo2MDQ6XCJJbnB1dDogbeG6o25nICRLXzEsIEtfMiwgLi4uLCBLX04kIMSRxrDhu6NjIHPhuq9wIHjhur9wIHbDoCBwaOG6p24gdOF7WyYqJl19u60gJEskIGPhuqduIHTDrG0uIEdp4bqjIHPhu60NCiROKzEgPSBGX3trKzF9LiBMxrB1IMO9IGluZGV4IGPhu6dhIG3huqNuZyBi4XtbJiomXX26r3QgxJHhuqd1IDEkDQoNClAxLiBbS2jhu59pIHThuqFvXSBpID0gRltrXSwgcCA9IEZbay0xXSwgcSA9IEZbay0yXQ0KUDIuIFtTe1smKiZdfW8gc8OhbmhdLg0KICAgIGlmIEtbaV0gJmx0OyBLOiBnbyB0byBQMy4NCiAgICBlbHNlIGlmIEtbaV0gJmd0OyBLOiBnbyB0byBQNC57WyYqJl19DQogICAgZWxzZTogcmV0dXJuIGk7DQpQMy4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gdHLDoWldDQogICAgaWYgcSA9IHtbJiomXX0wOiByZXR1cm4gLTENCiAgICBlbHNlOg0KICAgICAgICBpIC09IHENCiAgICAgICAgKHAsIHEpID0gKHEsIHAtcSkNCiAgICAgICAge1smKiZdfWdvIHRvIFAyDQpQNC4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gcGjhuqNpXQ0KICAgIGlmIHAgPSAxOiByZXR1cm4gLTF7WyYqJl19DQogICAgZWxzZToNCiAgICAgICAgaSArPSBxDQogICAgICAgIHAgLT0gcQ0KICAgICAgICBxIC09IHANCiAgICAgICAgZ28gdG8gUHtbJiomXX0yDQpcIjt7WyYqJl19[[/code]]

Bài tập

  • Thiết kế thuật toán cho trường hợp $N \geq 0$.
  • Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi
    nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Cây tìm kiếm Fibonacci với k=6. Source: TAoCP, Vol 3, P417.

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm
kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay
vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với
$F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),1
cây Fibonacci được xây dựng như sau:

  1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
  2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci
    bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes
    tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử
($N+1=F_{k+1} = F_7 = 13$)), số internal nodes
$F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra,
ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có
$F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal
nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo
đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận
chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể”
có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã
nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát
của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của
giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần
tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số
cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với
fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở
đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử
đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$
nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer
recurrence. Nếu sử dụng Akra-Bazzi method
thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

TODO

Mình cũng không biết nên dịch internal nodes với external nodes thế nào cho hợp (node trong và node ngoài?). ^

Heroku là gì?

Heroku là dịch vụ cung cấp máy chủ miễn phí cho người dùng. Với cái giá phải trả 0$ cùng với vô vàn các addons hỗ trợ cực kỳ hữu ích thì đấy được coi là một trong những dịch vụ hấp dẫn khó cưỡng. Dù miễn phí nhưng nó có thể so sanh với các server trả phí.

Heroku hỗ trợ nhiều ngôn ngữ lập trình

  • NodeJS
  • Ruby
  • Python
  • PHP
  • Java
  • Scala
  • Clojure
  • Go
  • Kotlin

heroku-yeulaptrinh.pw

Cách sử dụng

Trước mình có code server-side bằng NodeJS rồi deploy(triển khai) lên Heroku. Qua một thời gian trải nghiệm, mình thấy Heroku không quá khó dùng nhưng cũng không quá đơn giản dành cho gà mờ. Sử dụng nó cũng tương tự như Github với một số câu lệnh cơ bản như:

(bạn phải download heroku CLI về)

Một số tính năng khác

Ngoài những tính năng trên heroku còn hỗ trợ nhiều tính năng khác:

  • Database miễn phí
  • SSL miễn phí
  • Hỗ trợ làm việc team
  • Liên kết với Github đơn giản

Bất tiện khi sử dụng

Cái gì miễn phí thì cũng có một số bất tiện của nó. Ở Heroku thì là:

  • Heroku chỉ cho người dùng 550 giờ mỗi tháng để sử dụng. Tuy nhiên bạn có thể tăng số lượng giờ đồng hồ sử dụng lên con số 1000 nếu như bạn cài đặt phương thức thanh toán vào trong tài khoản. 1000 giờ đồng hồ là quá đủ để blog cá nhân của bạn chạy êm ru cả tháng (31 ngày * 24 giờ = 744 giờ)
  • Sau 2 đến 3 giờ nếu server không có người truy cập thì server sẽ chuyển sang trạng thái ngủ.Về việc server bị tắt khi không có traffic, cách đơn giản nhất là tự tạo traffic cho nó. Cách dễ nhất là dùng Pingdom để ping trang blog của bạn thường xuyên giữ cho server không bị tắt.Cài đặt Pingdom khá đơn giản, chỉ việc điền thông tin và nhấn chừng 3-4 cái nút. Cài đặt tại:

Bạn có thể nâng cấp lên để trải nghiệm tốt hơn.

Có một số tips nhỏ mình muốn giới thiệu cho bạn:

Tip: Vấn đề SSL

(SSL là chứng chỉ bảo mật)

Nếu bạn dùng domain mặc định của heroku (*.herokuapp.com) thì bạn sẽ dùng SLL không phải trả tiền. Tuy nhiên nếu bạn muốn trỏ sang domain cá nhân của bạn thì SSL sẽ không còn.

Để có được SSL miễn phí thi ta dùng Cloudflare để làm DNS và Cloudflare hỗ trợ miễn phí kết nối Full SSL đến host.

Pipeline là gì?

Ở heroku có một khái niệm mới là pipeline. Pipeline mang đến cho người dùng giải pháp Test automation và Continuous Integration/Continuous Development(CICD).

Pipeline là kiến trúc cho phép song song hoá các công đoạn trong xử lý vài lệnh đồng thời

Bạn có thể tìm hiểu thêm trên mạng.

GSON là gì?

Gson là một thư viện java cho phép người sử dụng có thể chuyển đổi từ một đối tượng Java sang JSON và cũng có thể chuyển đổi từ một đối tượng JSON sang java.Gson có thể làm việc với đối tượng java tùy ý bao gồm các đối tượng tồn tại sẵn mà bạn không có source-code của chúng.

Việc dùng Gson rất dễ dàng, không tốn công parse và cũng giúp chúng ta đỡ nhầm lẫn hơn khi parse trực tiếp từ JSON sang java. Đặc biệt là khi làm việc với những chuỗi JSON có rất nhiều trường.

  • Mục tiêu của Gson:
    • Cung cấp đơn giản toJson()và fromJson()phương pháp để chuyển đổi các đối tượng Java để JSON và ngược lại.
    • Cho phép tồn tại trước đó đối tượng unmodifiable để được chuyển đổi sang và từ JSON.
    • Hỗ trợ mở rộng của Java Generics.
    • Cho phép đại diện tùy chỉnh cho các đối tượng.
    • Hỗ trợ đối tượng tùy tiện phức tạp (với phân cấp thừa kế sâu và sử dụng rộng rãi các loại generic).
  • Tài liệu về Gson
    • Gson API: Javadocs for the current Gson release
    • Gson user guide: This guide contains examples on how to use Gson in your code.
    • Gson Roadmap: Details of changes in the recent versions
    • Gson design document: This document discusses issues we faced while designing Gson. It also includes a comparison of Gson with other Java libraries that can be used for Json conversion

    Thắc mắc và hỏi đáp tại google-gson Google group.

  • Chi tiết hơn về GSON cũng như các tài liệu tham khảo liên quan có thể tham khảo trên link sau :https://github.com/google/gson

Cài đặt NodeJS và một số lỗi thường gặp

Cài đặt NodeJS trên Window và Mac OS

Có lẽ Window và Mac OS là hai nển tảng dễ cài đặt NodeJS nhất, bạn chỉ cần vào trang chủ của NodeJS

[[code]]czoyMDpcImh0dHBzOi8vbm9kZWpzLm9yZw0KXCI7e1smKiZdfQ==[[/code]]
Để tải về phiên bản mới nhất và cài đặt. Sau khi cài đặt thành công, bạn hãy mởi cmd (Window), terminal (Mac OS) để kiểm tra cài đặt đã thành công hay chưa, bằng cách gõ lệnh:
[[code]]czo5Olwibm9kZSAtdg0KXCI7e1smKiZdfQ==[[/code]]
Nếu xuất ra version của NodeJS tức là bạn đã cài đặt thành công. Tiếp theo là kiểm tra NPM – Công cụ quản lý package của NodeJS.
[[code]]czo4OlwibnBtIC12DQpcIjt7WyYqJl19[[/code]]
Nếu xuất ra version của NPM bạn đã cài đặt thành công NodeJS, giờ chỉ việc lên ý tưởng và bắt đầu một project. VD:

Cài đặt NodeJS trên Ubuntu (12.04, 16.00+)

Trên Ubuntu, chúng ta sẽ dùng apt để cài đặt NodeJS. Đầu tiên, bạn nên update tất cả package của hệ điều hành để đảm bảo việc cài đặt NodeJS không gặp vấn đề.

[[code]]czoyMjpcInN1ZG8gYXB0LWdldCB1cGRhdGUuDQpcIjt7WyYqJl19[[/code]]

Cài NodeJS

[[code]]czoyOTpcInN1ZG8gYXB0LWdldCBpbnN0YWxsIG5vZGVqcw0KXCI7e1smKiZdfQ==[[/code]]

Cài đặt NPM

[[code]]czoyNjpcInN1ZG8gYXB0LWdldCBpbnN0YWxsIG5wbQ0KXCI7e1smKiZdfQ==[[/code]]
Để kiểm tra NPM và NodeJS đã cài đặt được chưa:
[[code]]czoxOTpcIm5vZGVqcyAtdg0KbnBtIC12DQpcIjt7WyYqJl19[[/code]]
Đến đây bạn sẽ thắc mắc vì sao trên Window, Mac OS, ta dùng lệnh node -v nhưng sao trên Ubuntu lại là nodejs -v.

Lý do là vì Ubuntu có một thành phần của hệ thống “mang tên” node rồi, nên NodeJS sinh sau, đẻ muộn đành phải dùng “tên” mới.

Điều này gây ra một số lỗi khi bạn cài NodeJS modules làm cho việc cài đặt không thành công. Để khắc phục ta sẽ symlink biến môi trường node về nodejs bằng lệnh sau:

[[code]]czo0MjpcInN1ZG8gbG4gLXMgL3Vzci9iaW4vbm9kZWpzIC91c3IvYmluL25vZGUNClwiO3tbJiomXX0=[[/code]]
Bạn hãy kiểm tra lại version của NodeJS bằng cách:
[[code]]czo5Olwibm9kZSAtdg0KXCI7e1smKiZdfQ==[[/code]]

Cài đặt NodeJS trên CentOS

Đầu tiên bạn nên update các package của hệ điều hành bằng câu lệnh:

[[code]]czoyMDpcInN1ZG8geXVtIC15IHVwZGF0ZQ0KXCI7e1smKiZdfQ==[[/code]]
Trên CentOS, chúng ta ưu tiên cài đặt NodeJS bằng cách build source, để làm được điều này, ta cần cài đặt các công cụ cần thiết bằng lệnh:
[[code]]czo0ODpcInN1ZG8geXVtIC15IGdyb3VwaW5zdGFsbCBcXFwiRGV2ZWxvcG1lbnQgVG9vbHNcXFwiDQpcIjt7WyYqJl19[[/code]]
Sử dụng wget tải source NodeJS:
[[code]]czo1NzpcIndnZXQgaHR0cDovL25vZGVqcy5vcmcvZGlzdC92MC4xMC40L25vZGUtdjAuMTAuNC50YXIuZ3oNClwiO3tbJiomXX0=[[/code]]
Giải nén và cd vào thư mục source:
[[code]]czo0NjpcInRhciB6eGYgbm9kZS12MC4xMC40LnRhci5neg0KY2Qgbm9kZS12MC4xMC40DQpcIjt7WyYqJl19[[/code]]
Chạy file config để chuẩn bị build source: ./configure Và đây là bước quan trọng nhất, chúng ta sẽ bắt đầu build:
[[code]]czo2OlwibWFrZQ0KXCI7e1smKiZdfQ==[[/code]]
Khi quá trình này hoàn thành, ta chạy tiếp lệnh này:
[[code]]czoxNDpcIm1ha2UgaW5zdGFsbA0KXCI7e1smKiZdfQ==[[/code]]
Quá trình build source NodeJS đã hoàn thành, giờ bạn chỉ cần thực hiện bước kiểm tra xem NodeJS đã cài đặt thành công chưa như với Window, Mac OS, Ubuntu.

Một số lỗi thường gặp

Không cài đặt NodeJS module cho project được Nếu NPM đã cài đặt thành công nhưng khi chạy lệnh:

[[code]]czo3MjpcIm5wbSBpbnN0YWxsIHTDqm5fbW9kdWxlDQpIb+G6t2Mga2hpIGPDsyBmaWxlIHBhY2thZ2UuanNvbg0KbnBtIGluc3RhbGx7WyYqJl19DQpcIjt7WyYqJl19[[/code]]
Mà có lỗi xuất hiện, thì rất có thể NPM trên máy của bạn đang dùng là phiên bản cũ. Lệnh này sẽ update NPM với phiên bản mới nhất. Chỉ cần chạy lệnh:
[[code]]czoyMzpcInN1ZG8gbnBtIGluc3RhbGwgLWcgbnBtXCI7e1smKiZdfQ==[[/code]]

Giới thiệu về MongoDB

MongoDB là gì ?

Hiểu một cách nôm na thì MongoDB là một mã nguồn mở và là một tập tài liệu dùng cơ chế NoSQL để truy vấn, nó được viết bởi ngôn ngữ C++. Chính vì được viết bởi C++ nên nó có khả năng tính toán với tốc độ cao chứ không giống như các hệ quản trị CSDL hiện nay. Nếu như bạn biết sử dụng JSON thì trong MongoDB cũng có cấu trúc lưu trữ tương tự, chính vì thế nó có hiệu suất cao, tương tác nhanh và khả năng mở rộng tốt, nó hoạt động trên khái niệm collection và document.

  • Collection trong MongoDB là nhóm các tài liệu (document), nó tương đương với một bảng (table) trong CSDL thông thường nên mỗi collection sẽ thuộc về một database duy nhất. Tuy nhiên nó có một sự khác biệt đó là nó không có ràng buộc Relationship như các hệ quản trị CSDL khác nên việc truy xuất rất nhanh, chính vì thế mỗi collection có thể chứa nhiều thể loại khác nhau không giống như table trong hệ quản trị mysql là các field cố định.
  • Document trong MongoDB có cấu trúc tương tự như kiểu dữ liệu JSON, nghĩa là sẽ có các cặp (key => giá trị) nên nó có tính năng động rất lớn. Document ta có thể hiểu nó giống như các record dữ liệu trong MYSQL, tuy nhiên nó có sự khác biệt là các cặp (key => value) có thể không giống nhau ở mỗi document.

MongoDB hoạt động như thế nào?

mongodb-yeulaptrinh.pw

MongoDB hoạt động dưới một tiến trình ngầm service luôn mở một cổng (Cổng mặc định là 27017) để lắng nghe các yêu cầu truy vấn, thao tác từ các ứng dụng gửi vào sau đó mới tiến hành xử lý. Mỗi một bản ghi của MongoDB được tự động gắn thêm một field có tên “_id” thuộc kiểu dữ liệu ObjectId mà nó quy định để xác định được tính duy nhất của bản ghi này so với bản ghi khác, cũng như phục vụ các thao tác tìm kiếm và truy vấn thông tin về sau. Trường dữ liệu “_id” luôn được tự động đánh index (chỉ mục) để tốc độ truy vấn thông tin đạt hiệu suất cao nhất. Mỗi khi có một truy vấn dữ liệu, bản ghi được cache (ghi đệm) lên bộ nhớ Ram, để phục vụ lượt truy vấn sau diễn ra nhanh hơn mà không cần phải đọc từ ổ cứng. Khi có yêu cầu thêm/sửa/xóa bản ghi, để đảm bảo hiệu suất của ứng dụng mặc định MongoDB sẽ chưa cập nhật xuống ổ cứng ngay, mà sau 60 giây MongoDB mới thực hiện ghi toàn bộ dữ liệu thay đổi từ RAM xuống ổ cứng.

Ưu điểm của MongoDB

  • Dữ liệu lưu trữ phi cấu trúc, không có tính ràng buộc, toàn vẹn nên tính sẵn sàng cao, hiệu suất lớn và dễ dàng mở rộng lưu trữ.
  • Dữ liệu được caching (ghi đệm) lên RAM, hạn chế truy cập vào ổ cứng nên tốc độ đọc và ghi cao.

Nhược điểm của MongoDB

  • Không ràng buộc, toàn vẹn nên không ứng dụng được cho các mô hình giao dịch yêu cầu độ chính xác cao.
  • Không có cơ chế transaction (giao dịch) để phục vụ các ứng dụng ngân hàng.
  • Dữ liệu được caching, lấy RAM làm trọng tâm hoạt động vì vậy khi hoạt động yêu cầu một bộ nhớ RAM lớn.
  • Mọi thay đổi về dữ liệu mặc định đều chưa được ghi xuống ổ cứng ngay lập tức vì vậy khả năng bị mất dữ liệu từ nguyên nhân mất điện đột xuất là rất cao.

COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}

Tổng hợp tài liêu, đề thi môn Cơ Nhiệt

 Các hãy bạn trao đổi kết quả, lời giải bằng cách comment ở bên dưới bài viết. Để đáp án các đề được hoàn thiện hơn

Đề cương ôn tập

Đề thi cuối kỳ

co-nhiet-2017-yeulaptrinh

co-nhiet-16-yeulaptrinh

co-nhiet-2016-yeulaptrinh

co-nhiet-yeulaptrinh-14

Lời giải một số đề Cơ nhiệt cuối kỳ

https://drive.google.com/file/d/0BxaNmKNXkJWJWGxUUW12cTNyN3M/view?usp=sharing

https://drive.google.com/file/d/0B9WAwe4vPnvDV1pyRU9fVTlKbkk/view?usp=sharing

 

(Sẽ có cập nhập thêm)