Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
VMLP - Đường đi dài nhất |
Bạn được nhận xử lý một đồ thị. Đồ thị này được gọi là đơn đồ thị vô hướng, tức là giữa hai đỉnh u và v bất kì chỉ có tối đa một cung nối vô hướng.
Một đường đi đơn trên đồ thị là một dãy các đỉnh x1, x2, ..., xk sao cho luôn có cung nối giữa đỉnh xi và đỉnh xi + 1(1 ≤ i < k). Đường đi đơn là đường đi mà không có hai đỉnh nào lặp lại.
Độ dài đường đi là số đỉnh trên đường đi đó. Hãy tìm một đường đi đơn có độ dài lớn nhất có thể trên đồ thị đã cho.
Input
Input gồm nhiều dòng:
- Dòng thứ nhất: 2 số nguyên N và M, số đỉnh và số cạnh của đồ thị.
- M dòng tiếp theo: mỗi dòng ghi hai số nguyên u và v (u khác v), thể hiện cạnh (u, v) vô hướng trong đồ thị.
Output
Ouput gồm 2 dòng:
- Dòng thứ nhất là một số nguyên, độ dài đường đi đơn tìm được.
- Dòng thứ hai là dãy các đỉnh thể hiện đường đi đó.
Giới hạn
- N ≤ 1000, M ≤ 10000.
Cách tính điểm
Điểm tạm thời của thí sinh X (TPx) được tính theo công thức sau: gọi R là tỉ số giữa đáp án của thí sinh X và đáp án của ban tổ chức,
- Nếu R < 0.8: TPx = 100R;
- Nếu 0.8 ≤ R ≤ 1: TPx = 40 + 60(R - 0.8) / 0.2;
- Nếu R > 1: TPx = 100 + 100R / 3.
Điểm chính thức của thí sinh X (OPx) được tính theo công thức sau: gọi TPmax là điểm tạm thời cao nhất trong điểm tạm thời của các thí sinh:
- OPx = TPx / TPmax * 100.
Example
Input: 6 5
1 2
2 3
3 4
2 5
5 6
Output: 5
4 3 2 5 6
Lời giải trên sẽ được 100.0 điểm (chính thức) vì đường đi đã tìm được là tối ưu.
Lưu ý: lời giải của bạn sẽ được chấm thử trên 10 test (không bao gồm test đề) trong suốt thời gian diễn ra vòng thi này. Bộ test chính thức sẽ có nhiều test hơn và bao gồm cả 10 test trên.
Được gửi lên bởi: | VOJ Team |
Ngày: | 2012-05-26 |
Thời gian chạy: | 0.400s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | C C++ 4.3.2 CPP PAS-GPC PAS-FPC |
Nguồn bài: | Nguyễn Xuân Khánh |
hide comments
2020-11-13 04:53:10 Pham Dat
đồ thị vô hướng nhưng dùng sai khái niệm cung/cạnh. admin nên cập nhật lại đề. |
|
2019-05-15 13:04:06
⠄⠄⠄⣾⣿⠿⠿⠶⠿⢿⣿⣿⣿⣿⣦⣤⣄⢀⡅⢠⣾⣛⡉⠄⠄⠄⠸⢀⣿ ⠄⠄⢀⡋⣡⣴⣶⣶⡀⠄⠄⠙⢿⣿⣿⣿⣿⣿⣴⣿⣿⣿⢃⣤⣄⣀⣥⣿⣿ ⠄⠄⢸⣇⠻⣿⣿⣿⣧⣀⢀⣠⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⣿⣿⣿ ⠄⢀⢸⣿⣷⣤⣤⣤⣬⣙⣛⢿⣿⣿⣿⣿⣿⣿⡿⣿⣿⡍⠄⠄⢀⣤⣄⠉⠋ ⠄⣼⣖⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⢇⣿⣿⡷⠶⠶⢿⣿⣿⠇⢀ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⣿⣿⣿⣿⣿⣿⣷⣶⣥⣴⣿ ⢀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟ ⢸⣿⣦⣌⣛⣻⣿⣿⣧⠙⠛⠛⡭⠅⠒⠦⠭⣭⡻⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠄⠹⠈⢋⣽⣿⣿⣿⣿⣵⣾⠃ ⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⠄⣴⣿⣶⣄⠄⣴⣶⠄⢀⣾⣿⣿⣿⣿⣿⣿⠃⠄ ⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⠄⣿⣿⡀⣾⣿⣿⣿⣿⣛⠛⠁⠄⠄ |
|
2019-05-14 11:20:16
chao con cac |
|
2019-05-14 11:19:53
..................……………………….…._¸„„„„_ …………………….…………...„--~*'¯….….'\ ………….…………………… („-~~--„¸_….,/ì'Ì …….…………………….¸„-^"¯ : : : : :¸-¯"¯/' ……………………¸„„-^"¯ : : : : : : : '\¸„„,-" **¯¯¯'^^~-„„„----~^*'"¯ : : : : : : : : : :¸-" .:.:.:.:.„-^" : : : : : : : : : : : : : : : : :„-" :.:.:.:.:.:.:.:.:.:.: : : : : : : : : : ¸„-^¯ .::.:.:.:.:.:.:.:. : : : : : : : ¸„„-^¯ :.' : : '\ : : : : : : : ;¸„„-~"¯ :.:.:: :"-„""***/*'ì¸'¯ :.': : : : :"-„ : : :"\ .:.:.: : : : :" : : : : \, :.: : : : : : : : : : : : 'Ì : : : : : : :, : : : : : :/ "-„_::::_„-*__„„~" |
|
2019-05-14 11:10:03
tran duc manh xin chao hoang nghia hiep |