Lộ trình K xe tải

Buổi 48 — Min-Cost Max Flow
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cần điều phối $K$ xe tải đi từ trạm xuất phát $1$ đến trạm đích $N$ trên đồ thị có hướng gồm $N$ đỉnh và $M$ cung. Mỗi cung $(u, v)$ có chi phí đi qua là $w$.

Để tránh ùn tắc, không có hai xe tải nào được đi qua cùng một trạm trung gian (tức là các lộ trình phải phân biệt về đỉnh, ngoại trừ đỉnh $1$ và đỉnh $N$), và mỗi cung chỉ được đi qua tối đa bởi 1 xe.

Hãy tìm tổng chi phí nhỏ nhất cho $K$ xe tải, hoặc in ra -1 nếu không thể sắp xếp đủ $K$ lộ trình.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 200, 1 \le M \le 2000, 1 \le K \le 20$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N, 0 \le w \le 10^5$).
Dữ liệu ra
  • In ra tổng chi phí nhỏ nhất, hoặc -1 nếu không thể.
Ví dụ
Input Output
5 6 2
1 2 2
2 5 3
1 3 1
3 4 2
4 5 1
2 4 1
9
Giới hạn
  • $2 \le N \le 200, 1 \le M \le 2000, 1 \le K \le 20$.
  • Thời gian chạy: 2 giây.
Draft saved