我们可以YY一下，首先关于加油站费用，我们可以经过把一个点拆成两个点，中间连一条容量为1的边，费用为A，然后就是建加油站，我们可以把每一个空地的点，拆成四个点，两两相连，其中一个代表建加油站的费用C+A，另一个就是路过，无费用，然后对于X，Y坐标减少，我们也可以连一条费用为B的边即可。但是...咱们还不能表示汽车最多行驶K...所以之前的YY也是没有意义的...
然后看到了题解...跟星际实际上是一样的，需要建立K层图才行....
然后我们在新的图上考虑...对于新图上的 点 (i,j,l)(i,j表示坐标，l表示油量）,如果原图i,j是加油站，而l<>k(即油量未满）那么咱们得将 （i,j,l)与(i,j,k)连一条边，权值为A，否则按普通点处理。然后如果原图 i,j为空地，油量未满，我们也可以建立一个加油站，即 将 （i,j,l)与(i,j,k)连边，边权为 A+C，油量慢的话就不用建了。然后假设我们不加油，那么 我们给 (i,j,k) 与 （i+1,j,k-1)和 （i,j+1,k-1)连一条边权为0的边，然后把 (i-1,j,k-1)和(i,j-1,k-1)连一条边权为B的边，然后这样建好图之后跑最短路即可（网络流都不要了！），然后对于跑出来的结果，就是 min(d(n,n,p))(1<=p<=k)
上面的模型真是太精妙了咩...
写了一个模拟链表优化的邻接表，然后跑SPFA即可。（堆加dijkstra改天写一个） 至于拆点，我们对于第p层的 i,j个点可以拆为 (p-1)*n*n+(i-1)*n+j 。实际上就是类似N进制的东西...
注意上面连的全部都是有向边。 又一次傻×的忘记了SPFA最后找完u的所有邻接边之后要把它的 v[](表示是否在队列中）改为 false，Wa了半天...
program flow15;
const maxn=700000;
type
lin=record
v,w,pre:longint;
end;
var g:array[1..100,1..100]of longint;
n,max,a,b,c,tot:longint;
e:array[1..maxn]of lin;
last,d:array[1..maxn div 5]of longint;
que:array[0..maxn]of longint;
v:array[0..maxn div 5]of boolean;
function calc(i,j,p:longint):longint;{计算（i,j)油量为k的点的编号}
begin
exit(p*n*n+(i-1)*n+j);
end;
procedure addedge(u,v,w:longint); {给邻接表加边}
begin
inc(tot);
e[tot].v:=v;
e[tot].w:=w;
e[tot].pre:=last[u];
last[u]:=tot;
end;
procedure spfa(s:longint); {Spfa求最短路}
var tmp,u,l,r:longint;
begin
fillchar(que,sizeof(que),0);
fillchar(d,sizeof(d),1);
fillchar(v,sizeof(v),false);
l:=0;r:=1;que[l]:=s;
d[s]:=0;v[s]:=true;
while l<>r do
begin
u:=que[l];
tmp:=last[u];
while tmp<>0 do
begin
if d[e[tmp].v]>d[u]+e[tmp].w then
begin
d[e[tmp].v]:=d[u]+e[tmp].w;
if not v[e[tmp].v] then
begin
que[r]:=e[tmp].v;
r:=(r+1)mod maxn;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
v[u]:=false;
l:=(l+1)mod maxn;
end;
end;
function min(a,b:longint):longint;{不解释...}
begin
if a<b then exit(a) else exit(b);
end;
procedure init;
var i,j,k,u,v,ans:longint;
begin
read(n,max,a,b,c);
fillchar(last,sizeof(last),0);
tot:=0;
for i:=1 to n do
for j:=1 to n do
read(g[i][j]);
for i:=1 to n do
for j:=1 to n do
for k:=0 to max do {枚举分层图的每一个节点，然后分类讨论并加边}
begin
if (g[i][j]=1)and(k<>max)then {当前地区有油库且油量未满{必须加油}}
begin
u:=calc(i,j,k);
v:=calc(i,j,max);
addedge(u,v,a);
end;
if (g[i][j]=0)and(k<>max)then {当前地区无油库且油量未满{可以修一个油库并加油}}
begin
u:=calc(i,j,k);
v:=calc(i,j,max);
addedge(u,v,a+c);
end;
if (k<>0)and(g[i][j]=0)then {当前地区无油库，考虑向周围走}
begin
u:=calc(i,j,k);
if i<n then begin
v:=calc(i+1,j,k-1);
addedge(u,v,0);
end;
if j<n then begin
v:=calc(i,j+1,k-1);
addedge(u,v,0);
end;
if i>1 then begin
v:=calc(i-1,j,k-1);
addedge(u,v,b);
end;
if j>1 then begin
v:=calc(i,j-1,k-1);
addedge(u,v,b);
end;
end;
if (k=max)and(g[i][j]=1)then {当前地区有油库，且油量已满，不需要加油，考虑向四周走}
begin
u:=calc(i,j,k);
if i<n then begin
v:=calc(i+1,j,k-1);
addedge(u,v,0);
end;
if j<n then begin
v:=calc(i,j+1,k-1);
addedge(u,v,0);
end;
if i>1 then begin
v:=calc(i-1,j,k-1);
addedge(u,v,b);
end;
if j>1 then begin
v:=calc(i,j-1,k-1);
addedge(u,v,b);
end;
end;
end;
spfa(calc(1,1,max)); {跑SPFA}
ans:=maxlongint;
for i:=0 to max do
ans:=min(ans,d[calc(n,n,i)]);
write(ans);
end;
begin
assign(input,'f.in');reset(input);
init;
close(input);
end.
评论