Bộ nhỏ: lát cắt đỉnh trên đồ thị đường ngắn nhất

Gọi \(G\) là đồ thị, \(s\) là đỉnh lối vào và \(t\) là đỉnh chứa vũ khí bí mật.

Với bộ nhỏ, trước hết tìm khoảng cách ngắn nhất từ \(s\) tới \(t\), chẳng hạn bằng Dijkstra; gọi khoảng cách này là \(L\). Nếu \(K=0\), không thể cản đỉnh nào nên đáp án là \(L\).

Giả sử \(K>0\). Cản \(s\) luôn có lợi, nên thực hiện trước: giảm \(K\) đi một và tăng \(L\) thêm một. Tiếp theo, xét có thể tăng \(L\) thêm một nữa bằng cách cản các đỉnh khác hay không. Muốn vậy, mọi đường ngắn nhất từ \(s\) tới \(t\) phải chứa một đỉnh bị cản khác \(s\).

Lấy đồ thị con của \(G\) chứa toàn bộ các đỉnh và cạnh nằm trên một đường ngắn nhất từ \(s\) tới \(t\). Định hướng mỗi cạnh theo chiều của đường đi chứa nó.

Nếu có thể chọn nhiều nhất \(K\) đỉnh phủ mọi đường đi — ví dụ \(a,d\) trong hình — thì xóa các đỉnh ấy sẽ tách \(s\) khỏi \(t\). Vì vậy cần tìm lát cắt đỉnh nhỏ nhất và kiểm tra kích thước có quá \(K\) hay không. Chuyển thành lát cắt cạnh bằng cách tách mỗi đỉnh trừ \(s,t\) thành hai đỉnh nối bởi cạnh dung lượng 1; các cạnh gốc trở thành cạnh dung lượng vô hạn.

Lát cắt \(K\) đỉnh trong đồ thị trước tương ứng với lát cắt cạnh dung lượng \(K\) trong đồ thị mới. Trong ví dụ, cắt các cạnh nối hai nửa của \(a,d\) sẽ tách đồ thị. Theo định lý max-flow/min-cut, kích thước lát cắt cạnh nhỏ nhất bằng luồng cực đại. Nếu tồn tại luồng lớn hơn \(K\), đáp án là \(L\); nếu không, đáp án là \(L+1\).

Bộ lớn: đồ thị theo thời gian

Với các giá trị \(X=1,2,\ldots\), xét mệnh đề \(P(X)\): có thể cản nhiều nhất \(K\) đỉnh để ngăn đội bảo vệ đi từ \(s\) tới \(t\) trong thời gian \(\le X\) hay không. Giá trị \(X\) đầu tiên mà \(P(X)\) sai là đáp án.

Để kiểm tra \(P(X)\), lập đồ thị \(G'\) có một đỉnh cho mỗi bộ ba \((v,x,b)\), trong đó \(v\) là đỉnh của \(G\), \(0\le x\le X\), và \(b\) là đúng hoặc sai. Đỉnh \((v,x,\mathrm{false})\) biểu diễn việc đội bảo vệ có thể tới \(v\) ở thời điểm \(x\); \((v,x,\mathrm{true})\) biểu diễn việc họ có thể tới \(v\) và vượt qua vật cản ở thời điểm \(x\). Thêm các cạnh:

1. \((v,x,\mathrm{false})\to(v,x,\mathrm{true})\) với mọi \(v,x\): đi qua vật cản miễn phí; xóa một cạnh thích hợp tương đương đặt vật cản tại \(v\).
2. \((v,x,\mathrm{false})\to(v,x+1,\mathrm{true})\) với \(x<X-1\): đi qua vật cản không miễn phí.
3. \((v,x,\mathrm{false})\to(v,x+1,\mathrm{false})\) với \(x<X\): đứng yên một đơn vị thời gian.
4. \((v,x,\mathrm{true})\to(w,x+1,\mathrm{false})\) với \(x<X\) và mỗi cạnh \(vw\) của \(G\): đi qua một cạnh trong một đơn vị thời gian.

Đặt \(\sigma=(s,0,\mathrm{false})\) và \(\tau=(t,X,\mathrm{false})\). Khi không cản đỉnh nào:

• Có đường từ \(\sigma\) tới \((v,x,\mathrm{false})\) khi và chỉ khi bảo vệ có thể tới \(v\) không muộn hơn thời điểm \(x\).
• Có đường từ \(\sigma\) tới \((v,x,\mathrm{true})\) khi và chỉ khi bảo vệ có thể rời \(v\) không muộn hơn thời điểm \(x\).
• Có đường từ \(\sigma\) tới \(\tau\) khi và chỉ khi có thể đi từ \(s\) tới \(t\) trong thời gian \(\le X\).

Nếu một số đỉnh của \(G\) bị cản, các tính chất vẫn đúng khi xóa mọi cạnh loại 1 có \(v\) tương ứng là đỉnh bị cản. Do đó \(P(X)\) là bài toán lát cắt: có thể tách \(\sigma,\tau\) bằng cách cắt các cạnh loại 1 ứng với nhiều nhất \(K\) đỉnh của \(G\) hay không.

Trong \(G\), sau khi chọn vật cản, mọi đường tối ưu từ \(s\) tới \(t\) đi qua một đỉnh \(v\) đều đi qua nó cùng thời điểm; vì vậy cản \(v\) chỉ “hữu ích” tại một thời điểm. Tương tự trong \(G'\), với mỗi \(v\) có nhiều nhất một \(x\) mà việc cắt cạnh \((v,x,\mathrm{false})\to(v,x,\mathrm{true})\) là hữu ích.

Chứng minh chính thức: giả sử tập cạnh loại 1 bị xóa \(A\) tách \(\sigma,\tau\) và chứa hai cạnh tại cùng \(v\), ở \(x_0<x_1\). Nếu cả hai đều cần thiết thì có đường từ \(\sigma\) tới \((v,x_0,\mathrm{false})\) và \((v,x_1,\mathrm{false})\), đồng thời có đường từ \((v,x_0,\mathrm{true})\) và \((v,x_1,\mathrm{true})\) tới \(\tau\). Nhưng khi đó có thể ghép một đường từ \(\sigma\) tới \(\tau\) qua \((v,x_0,\mathrm{false})\), \((v,x_1-1,\mathrm{false})\) và \((v,x_1,\mathrm{true})\), mâu thuẫn với việc đã tách chúng. Vì vậy mọi tập cắt \(A\) đều có một tập con vẫn tách được và cắt nhiều nhất một cạnh cho mỗi đỉnh của \(G\).

Suy ra \(P(X)\) tương đương với khả năng tách \(\sigma,\tau\) bằng nhiều nhất \(K\) cạnh loại 1. Như bộ nhỏ, đây là max flow: đặt dung lượng 1 cho cạnh loại 1 và vô hạn cho mọi cạnh khác.

Có thể giải nhanh chuỗi bài toán luồng này mà không tính lại từ đầu mỗi khi tăng \(X\): chỉ thêm một lớp đỉnh và cạnh cho giá trị \(X\) mới rồi cập nhật luồng.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - World Finals - Taking Over The World, kho Google Coding Competitions (Apache-2.0).