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
#10419
silly boy (Thành viên)
ronaldinho+3
Không code nữa rồi
Bài viết: 736
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 12 năm trước   (+0)
Cái này đúng là ko đúng đâu bạn ạ
 
Đã lưu IP Đã lưu IP  
 
Vì tương lai con em chúng ta , kệ cha tương lai con em chúng nó
  Đã khóa chức năng gửi bài.
#10467
SNOW ANGEL (Thành viên)
cun+1
Ra đề chuyên nghiệp
Bài viết: 117
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 12 năm trước   (+1)
Bài đó công thức là: M - N + K với N là số đỉnh, M là số cạnh và K lá số thành phần liên thông.
Chứng minh:
1) Trường hợp chỉ có 1 thành phần liên thông: Ta xây dựng cây khung, mất N-1 cạnh, còn lại M-N+1 cạnh, thêm 1 cạnh nào vào ta cũng có 1 chu trình cơ sở -> số chu trình cơ sở trong trường hợp này là M-N+1.

2) Trường hợp có K thành phần liên thông. Đồ thị chia thành h đồ thị con liên thông, với số đỉnh, số cạnh của mỗi đồ thị con lần lượt là N[i] và M[i].
Số chu trình cơ sở mỗi đồ thị con là trường hợp 1: M[i]-N[i]+1.
=> số chu trình cơ sở tất cả là: Sum{ M[i] - N[i] + 1) = M - N + K. (*)
trong đó sum{M[i]} = M
sum{N[i]} = N
và tổng (*) có K phần tử
=> ĐPCM
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#10478
chulun (Thành viên)
canhteo+10
Không code nữa rồi
Bài viết: 605
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 12 năm trước   (+0)
SNOW ANGEL viết:
QUOTE:
Bài đó công thức là: M - N + K với N là số đỉnh, M là số cạnh và K lá số thành phần liên thông.
Chứng minh:
1) Trường hợp chỉ có 1 thành phần liên thông: Ta xây dựng cây khung, mất N-1 cạnh, còn lại M-N+1 cạnh, thêm 1 cạnh nào vào ta cũng có 1 chu trình cơ sở -> số chu trình cơ sở trong trường hợp này là M-N+1.

2) Trường hợp có K thành phần liên thông. Đồ thị chia thành h đồ thị con liên thông, với số đỉnh, số cạnh của mỗi đồ thị con lần lượt là N[i] và M[i].
Số chu trình cơ sở mỗi đồ thị con là trường hợp 1: M[i]-N[i]+1.
=> số chu trình cơ sở tất cả là: Sum{ M[i] - N[i] + 1) = M - N + K. (*)
trong đó sum{M[i]} = M
sum{N[i]} = N
và tổng (*) có K phần tử
=> ĐPCM :)

Nếu em ko nhầm thì đây là công thức Euler
bài này nếu có phần in ra các chu trình chắc hay hơn ^^
 
Đã lưu IP Đã lưu IP  
 
Wish you always love and be loved!

****************

  Đã khóa chức năng gửi bài.
#10554
just4one (Thành viên)
just4one+1
Nhắm mắt code không bug
Bài viết: 129
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 12 năm trước   (+0)
chulun viết:
QUOTE:
SNOW ANGEL viết:
QUOTE:
Bài đó công thức là: M - N + K với N là số đỉnh, M là số cạnh và K lá số thành phần liên thông.
Chứng minh:
1) Trường hợp chỉ có 1 thành phần liên thông: Ta xây dựng cây khung, mất N-1 cạnh, còn lại M-N+1 cạnh, thêm 1 cạnh nào vào ta cũng có 1 chu trình cơ sở -> số chu trình cơ sở trong trường hợp này là M-N+1.

2) Trường hợp có K thành phần liên thông. Đồ thị chia thành h đồ thị con liên thông, với số đỉnh, số cạnh của mỗi đồ thị con lần lượt là N[i] và M[i].
Số chu trình cơ sở mỗi đồ thị con là trường hợp 1: M[i]-N[i]+1.
=> số chu trình cơ sở tất cả là: Sum{ M[i] - N[i] + 1) = M - N + K. (*)
trong đó sum{M[i]} = M
sum{N[i]} = N
và tổng (*) có K phần tử
=> ĐPCM :)

Nếu em ko nhầm thì đây là công thức Euler :D
bài này nếu có phần in ra các chu trình chắc hay hơn ^^


Sorry, đúng là mình nhầm, công thức là M-N+K
Nếu đề bài yêu cầu in ra các chu trình thì mình chỉ có cách O(M*N) là: Với mỗi TPLT tìm một cây khung, với mỗi cạnh (u,v) thuộc TPLT đó mà không nằm trong cây khung, tìm LCA của chúng và in ra cạnh u-->v + đường đi từ v --> LCA --> u..
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#18623
The immortal (Thành viên)
the_immortal
Super fast coder
Bài viết: 61
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 11 năm, 4 tháng trước   (+0)
SNOW ANGEL viết:
QUOTE:
Bài đó công thức là: M - N + K với N là số đỉnh, M là số cạnh và K lá số thành phần liên thông.
Chứng minh:
1) Trường hợp chỉ có 1 thành phần liên thông: Ta xây dựng cây khung, mất N-1 cạnh, còn lại M-N+1 cạnh, thêm 1 cạnh nào vào ta cũng có 1 chu trình cơ sở -> số chu trình cơ sở trong trường hợp này là M-N+1.

2) Trường hợp có K thành phần liên thông. Đồ thị chia thành h đồ thị con liên thông, với số đỉnh, số cạnh của mỗi đồ thị con lần lượt là N[i] và M[i].
Số chu trình cơ sở mỗi đồ thị con là trường hợp 1: M[i]-N[i]+1.
=> số chu trình cơ sở tất cả là: Sum{ M[i] - N[i] + 1) = M - N + K. (*)
trong đó sum{M[i]} = M
sum{N[i]} = N
và tổng (*) có K phần tử
=> ĐPCM :)

Lúc đầu em ko biết cái này nên wa mất 2 lần
mà em cũng ko hiểu sao mình lại wa
thuật của em là với 1 mỗi cạnh chưa đánh dấu (lúc đầu chưa đánh dấu cạnh nào) xét xem có chu trình nào đi qua 2 cạnh này ko . nếu có thì chọn chu trình ngắn nhất rồi đánh dấu các cạnh lại
em ngồi vẽ mãi ko tìm đc test nào sai , các pro cho em xin trường hợp sai đc ko ạ
em cám ơn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#30254
travian (Thành viên)
thong93-
Nhắm mắt code không bug
Bài viết: 121
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 10 năm, 4 tháng trước   (+0)
Ai AC bài này rồi cho em bộ test được không?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#30255
ruacon (Thành viên)
dinhcamnhung-
Nhắm mắt code không bug
Bài viết: 219
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 10 năm, 4 tháng trước   (+0)
Test tự random ah anh?
 
Đã lưu IP Đã lưu IP  
 
Tạm biệt vnoi.
  Đã khóa chức năng gửi bài.
#44451
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)
bài ni em xài hợp nhất dần cây
nếu số cạch nạp = n - 1 thì sẽ có
một thành phần liền thông
còn nếu mà nạp không đến n - 1 cạch
thì số thành phần liên thông tính
như thế nào?
mong các anh giúp đở
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#44452
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)
m-n+t (t là số thành phần liên thông)
 
Đã 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.
#44465
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 đang hỏi tính t như thế nào mà
 
Đã 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