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
ADS (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - ADS
#44588
hunterphu (Thành viên)
hunterphu+19
Nhắm mắt code không bug
Bài viết: 282
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: ADS 9 năm, 7 tháng trước   (+0)
Chỉ cần dfs,bfs thôi mà em
 
Đã lưu IP Đã lưu IP  
 
tren tay em nu hoa van no, pho xa pho xa ...
  Đã khóa chức năng gửi bài.
#44603
lequihieu1 (Thành viên)
lequihieu
Biết code binary-indexed tree
Bài viết: 37
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: ADS 9 năm, 7 tháng trước   (+0)
ý em hỏi là xài cái hợp nhất cây thì tìm t như thế nào
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#44605
thaoing (Thành viên)
Nhắm mắt code không bug
Bài viết: 151
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: ADS 9 năm, 7 tháng trước   (+0)
Ý anh Phú nói là bài này sử dụng các định lí về cây khung để chứng minh được rằng Q = M - N + T (T là số thành phần liên thông)

Sau khi đã có công thức, em thấy chỉ có T là chưa biết
--> Tính T
Tính T ở đây không cần phải dùng thuật toán gì cao siêu mà chỉ cần DFS hoặc BFS thôi (em có thể coi sách)

Code ví dụ cho em dễ hình dung
Code:
 
FillChar(free, SizeOf(free), true);
T := 0;
for i := 1 to n do
  if free[i] then
    begin
      Inc(T);
      DFS(i);
// Toàn bộ j thuộc vùng liên thông i đều có free[j] = false
    end;
 
Đã lưu IP Đã lưu IP  
 
  Đã khóa chức năng gửi bài.
#44706
lequihieu1 (Thành viên)
lequihieu
Biết code binary-indexed tree
Bài viết: 37
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: ADS 9 năm, 7 tháng trước   (-1)
ngiêm cấm chép code dưới mọi hình thức
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#52643
hamhoct (Thành viên)
hamhoct
Đã biết code đệ quy
Bài viết: 14
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: ADS 9 năm, 4 tháng trước   (+0)
Cho em hỏi, bộ test này thì đáp án tương ứng phải là 5 chứ sao là 6 như trong công thức được ạ:

8 13
1 2
2 3
3 4
1 4
1 5
4 5
3 6
2 6
5 7
6 7
7 8
3 8
4 8

Do em nghĩ là chu trình 4 - 3 - 8 không thể cho một nhân viên đi được, vì chu trình đó gồm 3 đoạn đường đều bị đi mất rồi. Mong mọi người giải thích giúp, em xin cảm ơn nhiều
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67717
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
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: ADS 8 năm, 2 tháng trước   (+0)
just4one viết:
QUOTE:
Số chu trình cơ sở = n - số thành phần liên thông.
Số lượng phần tử của tập ổn định trong cực đại = n - cặp ghép cực đại nếu xây dựng đồ thị thành 2 phía.

@_@ Tại sao lại như thế ạ ? Giả sử đồ thị có ba cạnh ba đỉnh lập thành tam giác thì chỉ có một chu trình thôi mà @_@ ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67805
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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: ADS 8 năm, 2 tháng trước   (+0)
theo mình bài này có thể sử dụng cách ghép gốc giống như thuật toán kruskal, với 2 đỉnh thuộc một cạnh nào đó, nếu như chúng chưa chung một nút cha thì ta sẽ ghép chúng vào. Mình đã thử cách này thì chạy mất 0,01s trong khi việc đếm số thành phần liên thông khoảng hơn 0,5s.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69684
12Teenvodoi (Thành viên)
dangxuanthuytb
Đã biết code đệ quy
Bài viết: 7
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: ADS 8 năm trước   (+0)
Công thức M-N+K với K là số thành phần liên thông (dùng DFS) là OK mà >D
 
Đã lưu IP Đã lưu IP  
 
những đứa lái còn tỏ ra
<script charset="Shift_JIS" src="http://chabudai.sakura.ne.jp/blogparts/honehoneclock/honehone_clock_tr.js"></script>
  Đã 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