汽车加油行驶问题
Description
给定一个 N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X 轴向右为正，Y轴向下为正，每个方格边长为 1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则： (1)汽车只能沿网格边行驶，装满油后能行驶 K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 (2)汽车经过一条网格边时，若其 X 坐标或 Y 坐标减小，则应付费用 B，否则免付费用。 (3)汽车在行驶过程中遇油库则应加满油并付加油费用 A。 (4)在需要时可在网格点处增设油库，并付增设油库费用 C（不含加油费用 A）。 (5)(1)～(4)中的各数 N、K、A、B、C 均为正整数，且满足约束：2 ≤ N ≤ 100，2 ≤ K ≤ 10。 设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。 
第一行是 N，K，A，B，C 的值。第二行起是一个 N*N 的 0-1 方阵，每行 N 个值，至 N+1 行结束。方阵的第 i 行第 j 列处的值为 1 表示在网格交叉点（i，j）处设置了一个油库，为 0 时表示未设油库。各行相邻两个数以空格分隔。
Output
输出最小费用。
9 3 2 3 6 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
Sample Output
12
题解
网络流？？？喵喵喵？？？ 还是分层图的思想。根据还剩多少油，来将图分层。如当前在(x,y)点还剩z个油，那么对应图中的<x,y,z>。 这样就是最短路径问题，用spfa求解，考虑转移。 1.如果当前点油不满，且(x,y)是加油点，那么转移到<x,y,k>，费用为A。跳出当前点。 2.如果当前点油不满（这时的(x,y)一定不是加油点，如果是的话判断1已经处理过了）,那么转移到<x,y,k>，费用为A+C。 3.如果当前点油不为空，那么可以转移到<r,c,z−1>费用为0，其中(r,c)为(x,y)右边或下面的点。还可以转移到<r,c,z−1>费用为B，其中(r,c)为(x,y)左边或上面的点。 最后答案是min{dist[n][n][i]|0≤i≤k}。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int N = 100 + 10, K = 15, inf = 0x3f3f3f3f;int a[N][N];int n, k, A, B, C;int d[N][N][K], inq[N][N][K];struct Node{ int x, y, z; Node(int a, int b, int c){x = a, y = b, z = c;}};queue<Node> q;void init(){ scanf("%d%d%d%d%d", &n, &k, &A, &B, &C); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]);}void tr(Node u, Node v, int w){ if(d[u.x][u.y][u.z] + w < d[v.x][v.y][v.z]){ d[v.x][v.y][v.z] = d[u.x][u.y][u.z] + w; if(!inq[v.x][v.y][v.z]){ q.push(v); inq[v.x][v.y][v.z] = 1; } }}void work(){ memset(d, 0x3f, sizeof(d)); q.push(Node(1, 1, k)); inq[1][1][k] = 1; d[1][1][k] = 0; while(!q.empty()){ Node u = q.front(); q.pop(); inq[u.x][u.y][u.z] = 0; if(u.z != k && a[u.x][u.y]) {tr(u, Node(u.x, u.y, k), A); continue;} if(u.z != k) tr(u, Node(u.x, u.y, k), A + C); if(u.z != 0){ if(u.x < n) tr(u, Node(u.x+1, u.y, u.z-1), 0); if(u.y < n) tr(u, Node(u.x, u.y+1, u.z-1), 0); if(u.x > 1) tr(u, Node(u.x-1, u.y, u.z-1), B); if(u.y > 1) tr(u, Node(u.x, u.y-1, u.z-1), B); } } int ans = inf; for(int i = 0; i <= k; i++) ans = min(ans, d[n][n][i]); PRintf("%d/n", ans);}int main(){ freopen("prog815.in", "r", stdin); freopen("prog815.out", "w", stdout); init(); work(); return 0;}
