网络流24题之十五汽车加油行驶问题

填坑

地址：cv1912

样例输入 Sample Input

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

模型

分层图最短路径问题。

实现

按照油箱中剩余油量建立K层图，汽车在地图上点i，剩余油量为l时，对应点为<i,l>。

1、如果油箱不满(l<K)，点i为油库点，从<i,l>到<i.top>建立一条权值为A的有向边。
2、如果油箱不满(l<K)，点i不为油库点，从<i,l>到<i.top>建立一条权值为A+C的有向边。
3、如果油箱不为空，i不为油库点，每层l从<i.l>到<j.l-1>建立一条权值为0的有向边，其中j为i的右边或下边相邻的一个顶点；从<i.l>到<j.l-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。
4、如果油箱不为空，i为油库点，从<i.K>到<j.K-1>建立一条权值为0的有向边，其中j为i的右边或下边相邻的一个顶点；从<i.K>到<j.K-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。

求从<(1,1),K>的单源最短路径，到达目标的最小费用就是Min{dist[<(N,N),k>] | 0 <= k <= K }

代码

#include <cstdio>
#include <cstring>
#include <queue>
#define L 15
#define N 105
using namespace std;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node
{
    int k,x,y;
    node(int a,int b,int c):k(a),x(b),y(c){}
    node(){}
}s,t;
int tot,map[N][N],id[N][N],dis[L][N][N],vis[L][N][N];
int n,m,x,y,z,a,b,c,f,K;
int spfa()
{
    int fee1,fee2;
    queue<node>que;
    memset(dis,0x3f,sizeof dis);
    dis[s.k][s.x][s.y]=0;
    vis[s.k][s.x][s.y]=1;
    que.push(s);
    while(!que.empty())
    {
        node now=que.front();que.pop();vis[now.k][now.x][now.y]=0,fee1=0;
        if (!now.k) continue; //without gas
        for (int i=fee1=0;i<4;i++)
        {
            int xx=now.x+dir[i][0],yy=now.y+dir[i][1];
            if (!id[xx][yy]) continue;
            if (i==2) fee1=b;
            if (!map[xx][yy])
            {
                fee2=c;//new gas station. if there is a gas station, you **must** add gas
                if (now.k && dis[now.k-1][xx][yy]>dis[now.k][now.x][now.y]+fee1)
                {
                    dis[now.k-1][xx][yy]=dis[now.k][now.x][now.y]+fee1;
                    if (!vis[now.k-1][xx][yy]) vis[now.k-1][xx][yy]=1,que.push(node(now.k-1,xx,yy));
                }
            }
            else fee2=0;
            if (dis[K][xx][yy]>dis[now.k][now.x][now.y]+a+fee1+fee2)
            {//add the gas
                dis[K][xx][yy]=dis[now.k][now.x][now.y]+a+fee1+fee2;
                if (!vis[K][xx][yy]) vis[K][xx][yy]=1,que.push(node(K,xx,yy));
            }
        }
    }
    int ans=0x3f3f3f3f;
    for (int i=0;i<=K;i++)
        ans=min(ans,dis[i][t.x][t.y]);
    return ans;
}
main()
{
    int sum=0;
    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",&map[i][j]),id[i][j]=++sum;
    s=node(K,1,1),t=node(0,n,n);
    printf("%d",spfa());
}

网络流24题之十五 汽车加油行驶问题

网络流24题之十五汽车加油行驶问题