Xét đồ thị có hướng ~G~ gồm ~n~ đỉnh và ~m~ cạnh, trong đó mỗi cặp ~(u, v)~ trong danh sách được biểu diễn bằng một cạnh có hướng ~u \to v~ trên ~G~. Bài toán yêu cầu tìm một số các chu trình đơn trên ~G~ và gán trọng số dương cho các chu trình này sao cho:

• Mọi cạnh ~u \to v~ được bao bởi ít nhất một chu trình.
• Khi xét trọng số mỗi cạnh là tổng trọng số các chu trình bao nó (gọi trọng số này là ~w(u \to v)~), với mỗi đỉnh ~u~, trọng số các cạnh đi đến ~u~ là bằng nhau.

Đầu tiên, nhận thấy rằng khi ta xét các thành phần liên thông mạnh của ~G~, nếu có tồn tại một cạnh ~u \to v~ bất kì nối hai thành phần liên thông mạnh khác nhau, đáp án chắc chắn là NO (vì không có chu trình nào trong ~G~ bao cạnh ~u \to v~). Ta sẽ từ từ chứng minh qua từng subtask là đáp án sẽ là YES ở mọi trường hợp còn lại.

Ở các subtask sau, ta sẽ giả sử là mọi cạnh của ~G~ đều nối hai đỉnh thuộc cùng thành phần liên thông mạnh. Nhận xét thêm rằng nếu ~G~ có nhiều thành phần liên thông mạnh, ta có thể giải cho từng thành phần một, nên ở dưới ta sẽ giả sử ~G~ là một đồ thị liên thông mạnh.

Subtask 1

Ở subtask này, vì mỗi cạnh thuộc đúng một chu trình đơn (nếu có cạnh không thuộc chu trình đơn nào thì đáp án là NO), ta nhận xét là các cạnh đồ thị ~G~ có thể tách được thành các chu trình đơn khác nhau. Bởi thế, ta có thể làm như sau:

• Khi vẫn còn tồn tại cạnh trong ~G~, dùng DFS để lấy ra một chu trình đơn bất kì. Gán trọng số cho mọi cạnh của chu trình đơn này bằng ~1~ rồi xóa các cạnh này khỏi đồ thị.

Ta có thể chứng minh rằng cách làm này luôn đi qua hết mọi cạnh do nhận xét quan trọng sau:

Mọi đỉnh ở đồ thị ~G~ ban đầu có bậc vào bằng bậc ra. Sau mỗi bước của quá trình trên, tính chất này được bảo toàn.

Do thế, nếu vẫn còn tồn tại cạnh thuộc ~G~ đi từ ~u \to v~, ta có thể chứng minh được là còn đường đi từ ~v~ tới ~u~; DFS sẽ tìm được đường đi này để xóa cạnh ~u \to v~. Ngoài ra, ở cuối quá trình, mọi cạnh sẽ có trọng số bằng ~1~, vì thế cách làm này thỏa điều kiện đề bài. Ta có thể dễ dàng cài thuật toán này trong độ phức tạp ~O(n + m)~ (tuy nhiên, với giới hạn dư dả trong đề, ta có thể cài với độ phức tạp to hơn).

Subtask 2

Để tiếp cận subtask 2, ta sẽ giải bài toán theo hướng sau:

• Dựng trọng số cuối cùng của các cạnh trước.
• Từ các trọng số cạnh, tìm tập các chu trình có trọng số tạo ra được các trọng số cạnh này.

Đây là vì điều kiện tổng quát của nhận xét trong subtask 1 cho phép ta làm bài theo hướng này:

Giả sử ta đã dựng các trọng số cuối cùng của các cạnh. Điều kiện cần và đủ để tồn tại tập các chu trình có trọng số tạo ra được trọng số cuối cùng của cạnh là: với mọi đỉnh ~v~, tổng trọng số các cạnh vào ~v~ = tổng trọng số các cạnh ra ~v~.

Chứng minh: Dễ dàng nhận thấy đây là điều kiện cần. Để chứng minh đây là điều kiện đủ, xét thuật toán sau trên đồ thị ~G'~ là ~G~ đã gán trọng số:

• Khi vẫn còn cạnh trong ~G'~ có trọng số dương, dùng DFS trên các cạnh có trọng số dương để lấy ra một chu trình đơn bất kì. Gọi ~x~ là trọng số nhỏ nhất của các cạnh trên chu trình. Thêm chu trình này với trọng số là ~x~ vào tập đáp án, rồi giảm ~x~ khỏi trọng số tất cả các cạnh trong chu trình trên ~G'~.

Ta có thể chứng minh được là thao tác này chỉ dừng khi mọi cạnh có trọng số bằng ~0~ vì điều kiện trên được bảo toàn sau mỗi bước; ngoài ra, thao tác này dừng sau tối đa ~m~ bước, vì ở mỗi bước có thêm ít nhất một cạnh bằng ~0~.

Từ đây, ta chỉ cần quan tâm tới việc gán trọng số các cạnh của ~G~ sao cho:

• Với mỗi đỉnh, mọi cạnh vào đều có trọng số bằng nhau.
• Với mọi đỉnh, tổng trọng số cạnh vào bằng tổng trọng số cạnh ra.
• Trọng số mọi cạnh đều dương.

Với subtask 2, ta có thể làm như sau:

• Đầu tiên, gán trọng số ~1~ cho cạnh ~n \to 1~. Ta chứng minh được là nếu tồn tại đáp án sao cho trọng số của cạnh ~n \to 1~ khác ~1~, ta hoàn toàn có thể chia trọng số mọi cạnh xuống cho cùng một hằng số mà vẫn đảm bảo điều kiện cần và đủ trên.
• Từ đây, ta biết được trọng số ra của ~n~ là ~1~. Bởi mọi cạnh vào ~n~ phải có trọng số bằng nhau, gán trọng số các cạnh này là ~\frac{1}{in(n)}~, với ~in(u)~ là bậc vào của đỉnh ~u~.
• Tiếp theo, ta biết được trọng số ra của ~n - 1~ (vì ~n - 1~ chỉ có thể có cạnh ra đi tới ~n~, và ta đã gán trọng số các cạnh vào ~n~). Thực hiện lại thao tác gán cạnh vào ~n - 1~ như trên.
• Làm tương tự với đỉnh ~n - 2, n - 3, \dots, 1~.

Nhận xét rằng thao tác này luôn cho trọng số dương cho mọi cạnh. Ta có thể cài thuật toán này trong độ phức tạp ~O(m(n + m))~ hoặc ~O(nm)~ (do bước DFS).

Full

Nhận thấy rằng hai điều kiện sau:

• Với mỗi đỉnh, mọi cạnh vào đều có trọng số bằng nhau.
• Với mọi đỉnh, tổng trọng số cạnh vào bằng tổng trọng số cạnh ra.

đều có thể đưa về các phương trình tuyến tính, với mỗi biến thể hiện trọng số của một cạnh trên đồ thị. Từ đó, ta thu được một hệ phương trình tuyến tính mà ta có thể giải bằng khử Gauss.

Nhận xét rằng có ~m - n~ phương trình thu được từ điều kiện loại ~1~ (với mỗi đỉnh ~v~ có cạnh vào ~u_1 \to v, u_2 \to v, \dots, u_k \to v~, ta dựng các phương trình ~w(u_1 \to v) - w(u_2 \to v) = 0, \dots, w(u_{k - 1} \to v) - w(u_k \to v) = 0~) và ~n~ phương trình thu được từ điều kiện loại ~2~, hệ phương trình có ~m~ biến và ~m~ phương trình. Ngoài ra, do vế phải của mọi phương trình bằng ~0~, và hệ phương trình thực ra chỉ có ~m - 1~ phương trình độc lập với nhau, ta có thể thêm một phương trình gán một cạnh bất kì bằng ~1~ và vẫn sẽ giải ra một nghiệm cho trọng số các đỉnh.

Độ phức tạp ở đây là ~O(m^3)~ từ khử Gauss.

Tuy nhiên, ta vẫn chưa chứng minh được là đáp án thu được luôn có nghiệm dương. Ta sẽ chứng minh ở phần cuối.

Mở rộng: giải bài toán với ~n \le 200, 1 \le m \le n^2~ và chứng minh bài toán luôn có nghiệm dương

Nhận thấy rằng việc sử dụng mỗi biến cho một cạnh là không cần thiết. Thực tế, ta chỉ cần ~n~ biến ~var_1, var_2, \dots, var_n~ có ý nghĩa sau:

• ~var_u~ có giá trị bằng trọng số mọi cạnh vào đỉnh ~u~.

Ta không cần điều kiện thứ nhất nữa. Điều kiện thứ hai có thể được viết ra như sau:

• Với mọi ~u~, ~in(u) \cdot var_u = var_{v_1} + var_{v_2} + \dots + var_{v_k}~, với ~v_1, \dots, v_k~ là các đỉnh có cạnh trực tiếp từ ~u~.

Từ nhận xét này, ta đã có thể hoàn toàn giải bài toán với độ phức tạp là ~O(nm + n^3)~, với ~O(nm)~ từ phần DFS và ~O(n^3)~ là khử Gauss trên hệ phương trình ~n~ biến.

Để chứng minh hệ phương trình này luôn có nghiệm dương, ta thay biến ~var_u~ thành biến ~s_u~ có ý nghĩa là tổng trọng số cạnh vào đỉnh ~u~. Dễ chứng minh được ~var_u = \frac{s_u}{in(u)}~. Ta viết lại phương trình trên:

• Với mọi ~u~, ~s_u = \frac{s_{v_1}}{in(v_1)} + \frac{s_{v_2}}{in(v_2)} + \dots + \frac{s_{v_k}}{in(v_k)}~.

Nếu các bạn đã đọc về Markov chain, thì hệ phương trình trên nhìn giống hệt phương trình tìm stationary distribution của discrete Markov chain sau:

• Với mọi đỉnh ~v~, gán ~p(v, u) = \frac{1}{in(v)}~ nếu tồn tại cạnh ~u \to v~ trong ~G~.

Vì ~G~ là đồ thị liên thông mạnh, Markov chain được tạo ra cũng là đồ thị liên thông mạnh, hay nói cách khác là nó irreducible, và vì thế nó luôn tồn tại một stationary distribution. Nói cách khác, nếu ta giải stationary distribution của Markov chain này rồi thu đáp án dưới các biến ~s~, ta luôn thu được nghiệm dương.