B
P8906 [USACO22DEC] Breakdown P
一个有向完全图（包括自环），进行 \(n^2\) 次删边，问每次删边后从 \(1\) 到 \(n\) 的长为 \(k\) 的最短路长度，或指出不存在长为 \(k\) 的 \(1\) 到 \(n\) 的路径。
\(n\le 300\)，\(2\le k\le 8\)，\(1\le w_{i,j}\le 10^8\).
容易想到分层图，直接跑是 \(O(n^4k)\) 的。
考虑折半，对于所有点，记录从 \(1\) 开始经过 \(\lfloor\frac{k}{2}\rfloor\) 条边到达它，和从它开始经过 \(\lceil\frac{k}{2}\rceil\) 条边到达 \(n\) 的最短路。
先化删为加。添加一条边时，依次扫过分层图的每一层，若一个点被松弛过，将其所有出边松弛一遍。
时间复杂度 \(O(n^4k)\) 小常数不好卡。
#include<bits/stdc++.h>
#define ll long long
#define N 305
#define inf 1e12
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,k,_w[N][N];
int w[N][N],ans[N*N];
int X[N*N],Y[N*N];
struct Graph{
int d[N][5];bool vs[N][5];
int st,k;
void init(int x,int p){
memset(d,0x3f,sizeof(d));
d[x][0]=0,st=x,k=p;
}
void upd(int x){
memset(vs,0,sizeof(vs));
for(int i=0;i<k;i++)vs[x][i]=1;
for(int i=0;i<k;i++)
for(int u=1;u<=n;u++)
if(vs[u][i]){
for(int v=1;v<=n;v++){
if(d[v][i+1]>d[u][i]+w[u][v])
vs[v][i+1]=true,d[v][i+1]=d[u][i]+w[u][v];
}
}
}
}p1;
struct Graph2{
int d[N][5];bool vs[N][5];
int st,k;
void init(int x,int p){
memset(d,0x3f,sizeof(d));
d[x][0]=0,st=x,k=p;
}
void upd(int x){
memset(vs,0,sizeof(vs));
for(int i=0;i<k;i++)vs[x][i]=true;
for(int i=0;i<k;i++)
for(int u=1;u<=n;u++)
if(vs[u][i]){
for(int v=1;v<=n;v++){
if(d[v][i+1]>d[u][i]+w[v][u])
vs[v][i+1]=true,d[v][i+1]=d[u][i]+w[v][u];
}
}
}
}p2;
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
_w[i][j]=read(),w[i][j]=1e9;
for(int i=1;i<=n*n;i++)
X[i]=read(),Y[i]=read();
p1.init(1,k>>1),p2.init(n,k+1>>1);
for(int i=n*n;i;i--){
ans[i]=2e9;
for(int j=1;j<=n;j++)
ans[i]=min(ans[i],p1.d[j][k>>1]+p2.d[j][k+1>>1]);
if(ans[i]>=1e9)ans[i]=-1;
w[X[i]][Y[i]]=_w[X[i]][Y[i]];
p1.upd(X[i]),p2.upd(Y[i]);
}
for(int i=1;i<=n*n;i++)
printf("%d\n",ans[i]);
return 0;
}
C
构造一个单调不升的非负数列 \(\{b\}\)，最小化
\[\sum_{i=1}^{n}f(b_i,a_i)
\]
其中
\[f(x,y)=\begin{cases}x-y&x\ge y\\C&x<y\end{cases}
\]
\(n\le 10^6\)，\(0\le V\le 10^9\).