Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Chuẩn bị trước tuần thi quốc gia (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 9
CHỦ ĐỀ - Chuẩn bị trước tuần thi quốc gia
#12280
khanhoatink4 (Thành viên)
khanhoatink4
Super fast coder
Bài viết: 64
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
Anh ơi cho em hỏi trong bài làm nếu ta dùng hàm ngắt thời gian
thì tốt nhất là bao nhiêu hả anh ?Em thấy nhiều bài timelimit nhỏ
nhưng khi làm,chạy nhiều hơn mà vẩn điểm tối đa khó hiểu quá
 
Đã lưu IP Đã lưu IP  
 
trên bước đi của thành công không có dấu chân của kẻ lười biếng
  Đã khóa chức năng gửi bài.
#12282
congminh91 (Thành viên)
Super fast coder
Bài viết: 75
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
các bài kq là số thực mà yêu cầu
Xuất ra chính xác đến 3 chữ số phần thập phân
và Xuất ra chính xác đến hàng phần nghìn
Thì KQ có được làm tròn kô vậy?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12284
gachoi717 (Thành viên)
tem717
Đã biết code đệ quy
Bài viết: 15
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
Mấy enh ở ngoài hà nội có nghe sơ hở chi về cái đề thi quốc gia năm ni ko?
Cho em chút ý tưởng nào!
Thấy cái gì cũng phải học, mệt chết! Nếu mà có đề thì giới hạn được chỗ ôn! Khỏe hơn nhiều! Hehe!
Vậy enh em nào cho làm ơn chia sẽ với nha! Thank nhiều!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12285
congminh91 (Thành viên)
Super fast coder
Bài viết: 75
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
po' tay chu' na`y luo^n
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12288
gachoi717 (Thành viên)
tem717
Đã biết code đệ quy
Bài viết: 15
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
Em có một cuốn sách về đồ thị, trong đó có mấy thuật toán tìm đường đi ngắn nhất (Ford_bellman, floyd, dijkstra). Thấy cái nào nó cũng bảo là dùng cho đồ thị vô hướng, nhưng trong quá trình sử dụng thì em thấy cái nào cũng dùng được cho mọi loại đồ thị.?!?!?!.

Có 1 số điểm khác mà em không hiểu:
- dijkstra chỉ dùng cho đồ thị có trọng số không âm. Ai có thể giúp em hiểu rõ hơn cái này được không ạ? Em thấy tư tưởng của nó hoàn toàn có thể áp dùng cho đồ thị có trọng số âm.?!?!?!
- Floyd độ phức tạp O(n3) vậy có lẽ chỉ cần học dijkstra (n2) thôi các bác nhỉ? (Tất nhiên loại này muốn quên cũng khó )
- Ford_Bellman nó dùng cho đồ thị có trọng số âm nhưng không có chu trình âm. Độ phức tạp của nó cũng là O(n3). Chẳng khác chi cái thằng floyd... (hình như nó vẫn nhanh hơn nhưng xem ra không ăn thua).



Bác nào giỏi về mấy khoản ni làm ơn chỉ giùm thằng em cái! Xin căm ơn và không hậu tạ!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12290
khuc_tuan (Admin)
khuc_tuan+137
Admin
Bài viết: 1472
graph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
gachoi717 viết:
QUOTE:
- dijkstra chỉ dùng cho đồ thị có trọng số không âm. Ai có thể giúp em hiểu rõ hơn cái này được không ạ? Em thấy tư tưởng của nó hoàn toàn có thể áp dùng cho đồ thị có trọng số âm.?!?!?!

Tư tưởng của dijkstra là : coi như càng đi xa thì đường đi càng dài ( vì thế mỗi bước thuật toán chọn đỉnh có đường đi ngắn nhất hiện tại là nhỏ nhất và cố định ), chả có lý gì mà tư tưởng này áp dụng cho đồ thị trọng số âm được

QUOTE:
Floyd độ phức tạp O(n3) vậy có lẽ chỉ cần học dijkstra (n2) thôi các bác nhỉ? (Tất nhiên loại này muốn quên cũng khó )

Độ phức tạp lớn nhưng cài lại dễ, đi thi ta cần tìm hướng giải đơn giản nhất nhưng vẫn thỏa mãn giới hạn của đề bài, chứ không phải tìm hướng giải để chương trình chạy nhanh nhất có thể, dùng ít bộ nhớ nhất có thể.

QUOTE:
Ford_Bellman nó dùng cho đồ thị có trọng số âm nhưng không có chu trình âm. Độ phức tạp của nó cũng là O(n3).

Độ phức tạp là O(m*n) với m là số cạnh, cũng hữu ích trong nhiều trường hợp
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12291
tuanpham1991 (Thành viên)
yourfriends
Đã code là AC
Bài viết: 91
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
em thấy bellman_ford khi cài queue vòng thì nó cũng nhanh hơn so với dijktra
còn với dồ thị thưa thì nó nhanh ko kém ijk heap là mấy
 
Đã lưu IP Đã lưu IP  
 
always be yourself and nerver give up
  Đã khóa chức năng gửi bài.
#12292
pirate (Admin)
khanhptnk+108
Admin
Bài viết: 868
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
Dijkstra có độ phức tạp nhỏ là do bước tham lam (chọn ra d[i] có giá trị nhỏ nhất chưa được chọn). Bước này giúp tiết kiệm được việc sửa nhãn nhiều lần so với ford-bellman. Sở dĩ tham lam là đúng vì sau này nếu tồn tại một d[j] khác sao cho d[j]+c[j][i] < d[i] thì nó đã được chọn trước d[i] rồi. Điều này đúng nếu c[j][i] là số không âm. Nếu là số âm thì không còn chính xác nữa.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12294
khanhoatink4 (Thành viên)
khanhoatink4
Super fast coder
Bài viết: 64
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
Mấy anh cho em hỏi cái nửa,là danh sách kề so với dùng ma trận kề
dùng cái nào nhanh hơn;Bởi vì ta đã có free thì mảng hai chiều
giờ có thể lưu rất lớn rồi;Nên có lẹ không cần dùng danh sách kề để làm gì cả
Em nghe nói dùng danh sách kề chạy lâu hơn ma trận kề có dúng không anh
 
Đã lưu IP Đã lưu IP  
 
trên bước đi của thành công không có dấu chân của kẻ lười biếng
  Đã khóa chức năng gửi bài.
#12298
minhtri (Thành viên)
buiminhtri
Đã code là AC
Bài viết: 94
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Chuẩn bị trước tuần thi quốc gia 11 năm, 11 tháng trước   (+0)
khanhoatink4 viết:
QUOTE:
Mấy anh cho em hỏi cái nửa,là danh sách kề so với dùng ma trận kề
dùng cái nào nhanh hơn;Bởi vì ta đã có free thì mảng hai chiều
giờ có thể lưu rất lớn rồi;Nên có lẹ không cần dùng danh sách kề để làm gì cả
Em nghe nói dùng danh sách kề chạy lâu hơn ma trận kề có dúng không anh:? :? :?

dùng ma trận kề rất tốn mem, làm chương trình biên dịch lâu, nói chung với kích thước lớn thì nên dùng danh sách liên kết hoặc tổ chức theo kiểu foward star
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS