庐阳网站快速排名,太原视频剪辑培训机构哪个好,国内最好用的免费建站平台,网站建设做网站可以吗题目描述#xff1a; 题解#xff1a;
看了很多题解#xff0c;无论什么解法都绕不开分层图 在本题中加满油的车每次可以移动K步#xff0c;那么我们就可以建立一个K1层的分层图#xff0c;表示汽车油量k的状态#xff08;油量0…k#xff09;#xff0c;然后根据题目…题目描述 题解
看了很多题解无论什么解法都绕不开分层图 在本题中加满油的车每次可以移动K步那么我们就可以建立一个K1层的分层图表示汽车油量k的状态油量0…k然后根据题目要求建图 首先我们规定(k从1开始)第k层第i行第j列点编号为(k-1) * n * n (i-1) * n j 首先我们从第k层(i,j)建立一条边到第k1层(i,j),边权为0相当于车原地不动其实这一步可有可无 然后肯定是否到达油站来详细分析 当到达油站时油会加满所以无论当前为哪一层都要指向第一层指向一个边边权为a即加油费。然后从第一层的(i,j)向第二层的四个方向指向边因为当i和j减少时要化为b所以指向(i-1,j)和(i,j-1)时边权为b另外两个i1j和ij1边权为0当然要注意当前点是否在图的边缘以防止越界 当没到油站时我们要向下一层的四个方向指向边然后我们要模拟建立油站的情况该点所有层均要向第一层生成一个有向边边权为建立油站的费用加油的费用即ac 然后跑最大流或者spfa都可以
代码
结合代码分析分析
#includecstdio
#includecstring
#includequeue
#includealgorithm
using namespace std;const int INF2e9;int n,k,p,b,c,cnt;
int head[350005],dis[350005],q[900005];
bool vis[350005],oil;
struct node{int next,v,dis;
}a[900005];void add(int x1,int y1,int z1,int x2,int y2,int z2,int dis){int un*n*(z1-1)(x1-1)*ny1;int vn*n*(z2-1)(x2-1)*ny2;a[cnt](node){head[u],v,dis};head[u]cnt;
}void spfa(){for(int i1;in*n*(k1);i) dis[i]INF;queueintq; //int hd1,tl1;int s1;q.push(1);vis[s]1;dis[1]0;while(!q.empty()){int uq.front();q.pop();vis[u]0;for(int ihead[u];i;ia[i].next){if(dis[a[i].v]dis[u]a[i].dis){dis[a[i].v]dis[u]a[i].dis;if(!vis[a[i].v]){vis[a[i].v]1;q.push(a[i].v);}}}}
}int main(){scanf(%d%d%d%d%d,n,k,p,b,c);for(int i1;in;i){for(int j1;jn;j){scanf(%d,oil);
// for(int l1;lk;l)
// {
// add(i,j,l,i,j,l1,0);//走一步
// }if(oil){for(int l2;lk1;l){add(i,j,l,i,j,1,p);}if(in) add(i,j,1,i1,j,2,0);if(jn) add(i,j,1,i,j1,2,0);if(i1) add(i,j,1,i-1,j,2,b);if(j1) add(i,j,1,i,j-1,2,b);}else{for(int l1;lk;l){if(in) add(i,j,l,i1,j,l1,0);if(jn) add(i,j,l,i,j1,l1,0);if(i1) add(i,j,l,i-1,j,l1,b);if(j1) add(i,j,l,i,j-1,l1,b);}for(int l2;lk1;l){add(i,j,l,i,j,1,pc);}}}}spfa();int ansINF;for(int i1;ik1;i) ansmin(ans,dis[n*n*i]);printf(%d\n,ans);return 0;
}
