Đây là hướng làm của mình:

Để tìm được 1 nghiệm thỏa mãn, ta có thể quy về bài toán tìm 1 lát cắt s-t của đồ thị mà có kích thước < G (bạn có thể tìm hiểu thêm về lát cắt và lát cắt cực tiểu) -> có thể tìm bằng luồng

Với độ dài tối đa cho trước bất kì, chỉ có một số vị trí có thể đặt lính -> chỉ có một số cạnh có thể thuộc tập hợp cắt.

Như vậy với mỗi độ dài tối đa cho trước, bạn có thể xây đồ thị sao cho lát cắt cực tiểu tìm được trên đồ thị này chỉ có thể cắt các cạnh có thể đặt lính.

Mình chỉ gợi ý đến thế thôi