Coi các đảo là các đỉnh, các hải trình là các cạnh, trọng số 1 của các cạnh là thương giữa hàng bán được và độ dài, trọng số 2 của các cạnh là độ dài.

1, Ta kiểm tra đồ thị có phải chu trình Euler không, nếu là chu trình Euler thì kết quả là tổng trọng số 1 của các cạnh (do các cạnh luôn dương theo đề bài)

2, Nếu đồ thị không phải chu trình Euler thì chắc ta phải quay lui thôi :(. \(M, N \leq 100\) nên chắc được. Có thể dùng Dijkstra để tính khoảng cách ngắn nhất (tức tổng trọng số 2 nhỏ nhất) từ đỉnh xuất phát đến các đỉnh để tính độ dài đường về nếu duyệt đến các đỉnh này để hỗ trợ phần quay lui. Đừng lo nếu đường về vẫn bán được hàng vì mình cũng sẽ xét đến trường hợp này sau nên không sót nghiệm. Lưu ý: Không đi một cạnh nhiều hơn một lần ở lượt đi (chưa chứng minh được cái này, nhưng nếu một cạnh nhiều hơn 1 lần thì có trường hợp bị lặp vô tận)

P/S: Test ví dụ có sai không nhỉ, \(1 \rightarrow 4 \rightarrow 5 \rightarrow 1\) đã được khoảng hơn 5 đơn vị lợi nhuận rồi mà? Mà nếu đỉnh \(1\) còn được đi hơn 2 lần thì kết quả còn hơn nữa!

Còn nếu muốn tìm hải trình mang nhiều lợi nhuận nhất có thể đi được thì ta tìm trọng số 1 lớn nhất trong các cạnh thuộc thành phần liên thông chứa đỉnh 1

Chặt nhị phân kết quả và Ford-Bellman tìm chu trình âm để kiểm tra

Bạn có thể trình bày rõ hơn được không 

Gọi \(r\) là lợi nhuận của hành trình cực đại \(W\)  với \(u\) là điểm xuất phát. Không mất tính tổng quát giả sử \(W\) là duy nhất. Do đó, với mọi hành trình \(\bar{W} = \{v_0 = u, v_2,\ldots, v_{k+1} = u\} \) đều có lợi nhuận \(< r\).Từ đó suy ra\(\frac{C_1 + C_2 + \ldots + C_k}{D_1 + D_2 + \ldots +D_k } < r \Rightarrow (rD_1-C_1) + (rD_2 -C_2 ) + \ldots + (rD_k - C_k ) > 0\) trong đó \(C_i,D_i\)là lượng hàng hóa bán được và độ dài cạnh \((v_i,v_{i+1})\).  Do đó, đồ thị với trọng số được đánh lại là \(rD_e-C_e\) với mọi cạnh \(e\) có một chu trình âm duy nhất là \(W\).  Thực ra là chu trình bằng 0 theo định nghĩa, nhưng ta có thể giảm \(r\) một lượng nhỏ để chu trình là âm mà không ảnh hưởng đến độ chính xác của thuật toán. Kiểm tra chu trình âm dùng Bellman Ford và tìm \(r\) dựa trên chặt nhị phân.

Đại khái giống như đồng chí prog_theory. Chặt nhị phân kết quả R. Dùng công thức trung bình cộng, dồn hết về một vế thì sẽ chỉ còn tổng các hạng tử R*D[u,v] - C[u,v]. Nhận thấy nếu R > đáp án của bài toán thì cả biểu thức sau khi biến đổi sẽ âm, nói cách khác là với đồ thị mà các cạnh là R*D[u,v] - C[u,v] thì tồn tại chu trình âm. Bởi vậy chỉ cần chặt nhị phân kết quả, với hàm check(x) là với tham số R = x, đồ thị có chu trình âm hay không? (sử dụng Ford - Bellman). Nếu check là không thì ghi nhận kết quả, tăng cận trái lên, và ngược lại. Về cơ bản là không có đoạn "chắc ta phải quay lui" như thằng bvd :)