题意

给定\(n\)点\(m\)条边，边权为\(1\)。初始点权为\(0\)，给定\(K\)，求将\(K\)个点的点权置为1时\(1\sim n\)的最短路最长是多少

做法

二分\(mid\)，求最短路大于\(mid\)，至少要选择多少点

\(i\in(0,mid)：S_{i,u}\longrightarrow T_{i,u}(flow:1)\)
\(i\in(0,mid-1)：S_{i,u}\longrightarrow T_{i+1,u}(flow:\infty)\)
\(i\in[0,mid)：T_{i,u}\longrightarrow S_{i+1,v},T_{i,v}\longrightarrow S_{i+1,u}(flow:\infty,(u,v)\in E)\)

求最小割

正确性：
考虑最短路的性质，不会割掉两条\(i\neq j,S_{i,u}\longrightarrow T_{i,u},S_{j,u}\longrightarrow T_{j,u}\)
当割掉\(S_{i,u}\longrightarrow T_{i,u}\)后，最短路走到\(u\)时必定时间\(+1\)