汽车加油行驶问题(分层图)

• 问题描述
• 单纯通过流量来限制问题中的流量似乎怎么建图也办不到，因此我们可以对原网格图进行分层，第0层代表当前油量为k，第k层代表当前油量为0，对于i层向其i+1层的相邻点按照题目要求连边，流量为inf，向左或者向上连边时费用为b；
• 处理油库：由于存在油库时为强制消费，因此对于油库点我们从第1层到第k层分别向第0层的这个点连边费用a，流量inf的边，并且油库点中只有第0层向其它位置的点连边，代表强制加油；
• 建油库：，第1到k层的每个点向第0层的该点连a+c费的边即可，流量为1；
• 源点向第0层的(1,1)连流量为1，费用为0的边，第1到k层的(n,n)点向汇点连流量为1，费用为0的边，跑最小费用最大流即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <fstream>
using namespace std;
const int maxn=1e6+10,maxm=5000005,inf=0x7f7f7f7f;
int cnt=1,n,last[maxn],d[maxn],inq[maxn],vis[maxn],cur[maxn],st=120005,flow,ans,flag,g[105][105],k,a,b,c,num;
struct edge{
    int v,next,w,f;
}e[maxm];
inline void add(int u,int v,int w,int f)
{
    e[++cnt].v=v;
    e[cnt].f=f;
    e[cnt].w=w;
    e[cnt].next=last[u];
    last[u]=cnt;
    e[++cnt].v=u;
    e[cnt].f=0;
    e[cnt].next=last[v];
    e[cnt].w=-w;
    last[v]=cnt;
}
bool spfa()
{
    queue<int>q;
    memset(inq,0,sizeof(inq));
    for(int i=1;i<=st;i++) d[i]=inf;
    d[0]=0;
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inq[u]=0;
        for(int i=last[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w,f=e[i].f;
            if(d[v]>d[u]+w&&f)
            {
                d[v]=d[u]+w;
                if(!inq[v])
                {
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return d[st]!=inf;
}
int dfs(int u,int dis)
{
    vis[u]=1;
    if(u==st||!dis) return dis;
    for(int i=cur[u];i;i=e[i].next)
    {
        cur[u]=e[i].next;
        int v=e[i].v,w=e[i].w,f=e[i].f;
        if(d[v]==d[u]+w&&f&&!vis[v])
        {
            vis[v]=1;
            int di=dfs(v,min(dis,f));
            if(di>0)
            {
                e[i].f-=di;
                e[i^1].f+=di;
                return di;
            }
        }
    }
    return 0;
}
bool dinic()
{
    while(spfa())
    {
        for(int i=0;i<=st;i++)
        cur[i]=last[i];
        memset(vis,0,sizeof(vis));
        while(int ml=dfs(0,inf))
        {
            ans+=d[st];
            flow+=ml;
            memset(vis,0,sizeof(vis));
        }
    }
    if(flow!=n) return 0;
    return 1;
}
void intt()
{
    for(int i=1;i<=cnt;i++)
    e[i].w=e[i].next=e[i].v=e[i].f=0;
    memset(last,0,sizeof(last));
    ans=flow=0;
    cnt=1;
}
int main()
{
    cin>>n>>k>>a>>b>>c;
    num=n*n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    scanf("%d",&g[i][j]);
    add(0,1,0,1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int poi=(i-1)*n+j;
            if(g[i][j])
            {
                for(int l=1;l<=k;l++)
                add(poi+l*num,poi,a,inf);
            }
            for(int l=0;l<k;l++)
            {
                if(g[i][j]&&l) break;
                if(i<n)
                add(l*num+poi,(l+1)*num+poi+n,0,inf);
                if(j<n)
                add(l*num+poi,(l+1)*num+poi+1,0,inf);
                if(i>1)
                add(l*num+poi,(l+1)*num+poi-n,b,inf);
                if(j>1)
                add(l*num+poi,(l+1)*num+poi-1,b,inf);
            }
            add(k*num+poi,poi,a+c,1);
        }
    }
    for(int i=1;i<=k;i++)
    add(i*num+num,st,0,1);
    dinic();
    cout<<ans;
    return 0;
}