题解 P4009 【汽车加油行驶问题】
唔姆
果然薯片+cola才是第一生产力
看这题明明是网络流24却没有一篇网络流的题解，我就来写一篇。我知道费用流肯定跑不过大佬们的最短路
首先如果没有油量的限制，这就是一个标准费用流了，直接把向右下走的连费0容1，往回走的连费B容1，原点向（1,1）连费0容1，（N,N）向汇点连费0容1，然后跑一边最小费用最大流就完事了。
但是问题来了，我们如何控制油量呢？？
我们想到了分层图这个好东西。我们把图变成k+1层，第零层代表：满油，第一层代表：k-1格油....第k层代表没油。
- 当此处没有加油站时，我们要把第i层（0<=i<K）连向第i+1层的下一个位置，第k层则直接向第1层同一位置连上一个流1费A+C的边，因为到了第k层不加油就没法走了
- 当此处有加油站时，因为题目里说了是强制消费！！！，所以我们只能从第1层到第k层都向第0层连上一个费A流1的边，代表加油，然后第0层再向别的点连边
- 特别的，原点我们只连向第一层的(1,1)，但是所以层的（n,n）都要连向汇点，因为不管你还剩多少油，能到(n,n)就OK了
贴上代码依旧是那毒瘤码风
#include<queue>
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXM 5000100
#define MAXN 1001000
using namespace std;
int to[MAXM],next[MAXM],w[MAXM],cost[MAXM],head[MAXN];
int n,m,S,T,ansl=0,ansc=0;
int cnt=-1;
int pre1[MAXN],pre2[MAXN],low[MAXN],dis[MAXN];
void link(int a,int b,int c,int d){
cnt++;
next[cnt]=head[a];
w[cnt]=c;
cost[cnt]=d;
to[cnt]=b;
head[a]=cnt;
cnt++;
next[cnt]=head[b];
w[cnt]=0;
cost[cnt]=-d;
to[cnt]=a;
head[b]=cnt;
}
bool spfa(){
queue<int>q;
fill(dis,dis+MAXN,66666666);
int vis[MAXN];
memset(vis,0,sizeof(vis));
q.push(S);
dis[S]=0;
vis[S]=1;
low[S]=66666666;
while(!q.empty()){
int now=q.front();
vis[now]=0;
q.pop();
for(int i=head[now];i!=-1;i=next[i]){
if (w[i]>0&&cost[i]+dis[now]<dis[to[i]]){
dis[to[i]]=dis[now]+cost[i];
low[to[i]]=min(low[now],w[i]);
pre1[to[i]]=now;
pre2[to[i]]=i;
if (!vis[to[i]]){
vis[to[i]]=1;
q.push(to[i]);
}
}
}
}
return dis[T]!=66666666;
}
void work(){
while(spfa()){
int now=T;
while(now!=S){
int y=pre2[now];
w[y]-=low[T];
w[y^1]+=low[T];
now=pre1[now];
}
ansl+=low[T];
ansc+=low[T]*dis[T];
}
}
int num(int a,int b){
return (a-1)*n+b;
}
int main(){
int K,A,B,C;
memset(head,-1,sizeof(head));
cin>>n>>K>>A>>B>>C;
S=0;T=MAXN-1;
link(S,num(1,1),1,0);
for(int i=0;i<=K;i++)
link(num(n,n)+10001*i,T,1,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int a;
scanf("%d",&a);
if (a)for(int k=1;k<=K;k++)link(num(i,j)+k*10001,num(i,j),1,A);
for(int k=0;k<K;k++){
if (a&&k)break;
if (i+1<=n)link(num(i,j)+k*10001,num(i+1,j)+(k+1)*10001,MAXM,0);
if (j+1<=n)link(num(i,j)+k*10001,num(i,j+1)+(k+1)*10001,MAXM,0);
if (i-1>0)link(num(i,j)+k*10001,num(i-1,j)+(k+1)*10001,MAXM,B);
if (j-1>0)link(num(i,j)+k*10001,num(i,j-1)+(k+1)*10001,MAXM,B);
}
link(num(i,j)+K*10001,num(i,j),1,A+C);
}
}
work();
cout<<ansc<<endl;
return 0;
}