题解 P4009 【汽车加油行驶问题】

吾王美如画

2019-02-07 23:07:14

Solution

# 唔姆 ~~果然薯片+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了 贴上代码~~依旧是那毒瘤码风~~ ```cpp #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; } ```