Mình là một người thường xuyên tạo test cho các bài tập trong Tin học, phần lớn các bài tập trên blog này mình đều tạo test. Nếu như việc tạo test cho những bài có dãy số tương đối đơn giản thì những bài đồ thị lại tương đối khó khăn vì có nhiều yêu cầu kèm theo như: đồ thị có các cạnh không được trùng nhau, số đỉnh lớn, số cạnh nhỏ (đồ thị thưa), đồ thị phải đảm bảo liên thông
Tất nhiên để viết chương trình tạo test đáp ứng những yêu cầu trên không phải là vấn đề lớn nhưng thời gian chạy quá lâu.
Do vậy mình có viết một chương trình tạo test để đáp ứng tất cả những yêu cầu trên với thời gian chạy ít (tạo đồ thị có 10^5 đỉnh và 10^6 cạnh trong thời gian 2 giây)
Chương trình của mình có khả năng tạo được tối đa 500 test
Các bạn có thể tải chương trình tại đây
Lưu ý:
+ Trước khi chạy tệp Create_Graph.cpp các bạn phải thiết lập trong tệp test.txt. Trong tệp test.txt có nhiều dòng, mỗi dòng gồm 2 số tương ứng là số cạnh và số đỉnh của đồ thị. Số dòng trong tệp cũng chính là số test của đồ thị
+ Các bạn cũng có thể thay đổi những thông số trong chương trình cho phù hợp với từng bài toán
- Dòng 3: số đỉnh tối đa trong đồ thị
- Dòng 4: Giá trị tối đa của trọng số trong đồ thị
- Dòng 5: Số lượng test tối đa muốn tạo
Dữ liệu ra: Gồm nhiều test, mỗi test nằm trong một thư mục, mỗi thư mục có 1 tệp tên là graph.inp có cấu trúc:
+ Dòng đầu là hai số nguyên dương n và m cho biết số đỉnh và số cạnh của đồ thị,
+ m dòng tiếp theo mỗi dòng ghi 3 số u, v, c trong đó c là trọng số của cạnh (u,v)
Thanks!
