Tóm tắt đề bài

Cho đồ thị có hướng gồm \(n\) đỉnh (phòng) và \(m\) cạnh (cổng dịch chuyển). Mỗi ngày bạn đi từ phòng \(1\) đến phòng \(n\) theo một đường đi có hướng. Mỗi cạnh chỉ được dùng tối đa một lần trong toàn bộ trò chơi (tức là giữa các ngày không được trùng cạnh). Mỗi lần đi qua một cạnh tốn \(1\) đồng xu.

Hãy tìm tổng số xu nhỏ nhất để chơi đúng \(k\) ngày (tức tìm \(k\) đường đi từ \(1\) đến \(n\) đôi một phân biệt theo cạnh), đồng thời in ra các lộ trình. Nếu không thể, in -1.

Phân tích

• Mỗi ngày là một đường đi từ \(1\) đến \(n\).
• Ràng buộc “mỗi cổng dùng tối đa một lần” \(\Rightarrow\) cần \(k\) đường đi edge-disjoint (không chung cạnh).
• Tổng chi phí chính là tổng số cạnh đã đi qua trong cả \(k\) ngày (vì mỗi cạnh giá \(1\)).
• Bài toán trở thành:
  • Gửi \(k\) đơn vị luồng từ \(1\) đến \(n\).
  • Mỗi cạnh có sức chứa \(1\) (để không dùng lại).
  • Chi phí mỗi cạnh là \(1\) (tối thiểu tổng số cạnh được dùng).

Đây là bài toán Min-Cost Flow: tìm luồng cực đại với chi phí nhỏ nhất, hoặc cụ thể hơn: tìm min-cost \(k\)-flow từ \(1\) đến \(n\).

Hướng giải quyết

Nhận xét

• Nếu tồn tại luồng giá trị \(k\) trong mạng với capacity \(1\) trên mỗi cạnh, ta thu được đúng \(k\) đường đi phân biệt theo cạnh (tính chất phân rã luồng nguyên).
• Vì tất cả capacity là số nguyên và ta tăng luồng theo từng đơn vị, thuật toán min-cost flow chuẩn sẽ cho luồng nguyên.
• Chi phí tối thiểu chính là tổng độ dài (số cạnh) của \(k\) đường đi.

Mô hình hoá thành Min-Cost Max-Flow

Tạo mạng:

• Mỗi cạnh gốc \((a \to b)\):
  • capacity \(= 1\)
  • cost \(= 1\)
• Tính min-cost để đẩy đúng \(k\) đơn vị luồng từ \(s=1\) đến \(t=n\).

Nếu không đẩy đủ \(k\) (tức flow \(<k\)) \(\Rightarrow\) in -1.

Thuật toán MCMF trong code (Dijkstra + tiềm năng)

Code dùng biến thể chuẩn:

1. Duy trì mảng tiềm năng pot[] để giảm chi phí cạnh (Johnson potentials), giúp chạy Dijkstra với trọng số không âm.
2. Mỗi vòng lặp:
   • Chạy Dijkstra trên chi phí hiệu chỉnh: \(c'(u,v)=c(u,v)+pot[u]-pot[v]\)
   • Nếu không tới được \(t\) thì dừng.
   • Cập nhật pot[v] += dist[v] cho mọi đỉnh reachable.
   • Vì mọi capacity gốc đều là \(1\), mỗi lần chỉ cần tăng luồng \(1\) đơn vị trên đường ngắn nhất tìm được.
   • Cộng chi phí thêm bằng pot[t] (sau cập nhật, pot[t] chính là độ dài đường đi ngắn nhất theo chi phí gốc trong lượt đó).

Tách \(k\) đường đi từ luồng đã tìm được

Sau khi có luồng \(k\):

• Một cạnh gốc \((u\to v)\) đã được dùng khi:
  • đó là cạnh “orig”
  • và capacity còn lại \(=0\) (vì ban đầu \(1\), dùng rồi sẽ giảm về \(0\))
• Lập danh sách kề usedAdj[u] gồm các cạnh đã dùng.

Sau đó, tách từng đường đi:

1. Lặp \(k\) lần:
   • DFS tìm một đường từ \(1\) đến \(n\) trong đồ thị usedAdj.
   • Ghi lại đường đi bằng mảng par[].
   • Sau khi tìm được, xóa các cạnh thuộc đường đó khỏi usedAdj để đảm bảo lần sau không dùng lại.
2. In ra mỗi đường theo định dạng:
   • số đỉnh trên đường
   • danh sách các đỉnh

Lưu ý:

• Do luồng là hợp lệ và các cạnh đã dùng tạo thành hợp của \(k\) đường (có thể kèm chu trình), thao tác “tìm đường rồi xóa cạnh” sẽ lần lượt lấy được đủ \(k\) đường từ \(1\) đến \(n\) trong bài này (theo đúng cách cài của code AC).

Độ phức tạp

Gọi \(F = k\).

• Mỗi lần tăng luồng chạy Dijkstra: \(O(m\log n)\).
• Tổng thời gian MCMF: \(O(k \cdot m \log n)\).
• Tách đường:
  • Mỗi lần DFS và xóa cạnh tổng cộng không vượt quá số cạnh đã dùng (\(\le m\)), nên xấp xỉ \(O(k\cdot m)\) trong cài đặt hiện tại (do erase tuyến tính).
• Bộ nhớ: \(O(n+m)\).

Với \(n \le 500\), \(m \le 1000\), \(k \le n-1\), cách này chạy tốt.