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
Trả lời: HIGHWAYS IOI 2006 (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Ủ ĐỀ - Trả lời: HIGHWAYS IOI 2006
#15120
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
HIGHWAYS IOI 2006 11 năm, 7 tháng trước   (+0)
Tóm tắt đề bài như sau: Cho một đồ thị vô hướng gồm n đỉnh và m cạnh. Yêu cầu bỏ đi một số cạnh sao cho đồ thị còn lại có các đỉnh đều có bậc lẻ. Số cạnh của đồ thị còn lại phải < n .
Các anh có thể giải thích cách làm và chứng minh tính đúng đắn của thuật toán giúp em được không ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#15124
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: HIGHWAYS IOI 2006 11 năm, 7 tháng trước   (+0)
Xét một cây khung có gốc. Xét các nút theo hướng từ lá lên tới gốc, nút nào có bậc chẵn thì bỏ cạnh nối với cha của nó đi -> bậc của các đỉnh có cha luôn lẻ, chỉ còn phải xét nút gốc.

Nếu bậc nút gốc lẻ -> có 1 cách thỏa mãn
Nếu bậc nút gốc chẵn -> vô nghiệm do mỗi khi bỏ 1 cạnh ta làm thay đổi tính chẵn lẻ của 2 đỉnh. Đồ thị này có số đỉnh bậc chẵn là lẻ.
 
Đã 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