「网络流24题」汽车加油行驶问题-题解

题目传送门: 「Luogu P4009」汽车加油行驶问题

题目大意

给出一个$N\times N$的网格,表示有加油站的位置
汽车要从$(1, 1)$走到$(N, N)$,装满油可以行驶$K$条边,且只能沿边行驶
服从以下规则

1. 可以无费用向右或向下走,但耗1点油
2. 向左走或者向上走时需要付费用$B$,并耗1点油
3. 在加油站处,若油没满,则必须付费用$A$,加满油
4. 可在没有加油站的位置开设加油站,费用$C$,并加满油,付费$A$
5. 在起点处,油量为$K$

求出最小费用

题解

明显是最小费用最大流(其实分层图最短路也可以解决,因为每条边的容量都为1)
分层建图,每层表示油量,第$0$层表示满油($K$),第$1$层表示油量为$K-1$,第$2$层表示油量为$K-2$,$…$

1. 对于每层每个节点,如果不是加油站,则从 该点 向 下一层的右边和下边的节点 接一条 容量为$1$,费用为$0$ 的边(规则1.)
2. 对于每层每个节点,如果不是加油站,则从 该点 向 下一层的左边和上边的节点 接一条 容量为$1$,费用为$B$ 的边(规则2.)
3. 对于每个节点,如果是加油站,则从 第$0$层的该点 按照上两条建边
4. 对于每个节点,如果是加油站,则从 除$0$层外的每层节点 向 第$0$层的该点 接一条 容量为$1$,费用为$A$ 的边(规则3.)
5. 对于每个节点,如果不是加油站,则从 第$K$层的该点 向 第$0$层的该点 接一条 容量为$1$,费用为$A+C$ 的边(规则4.)
6. 从 源点 向 第$0$层的$(1, 1)$节点 接一条 容量为$1$,费用为$0$ 的边
7. 从 每层的$(N, N)$节点 向 汇点 接一条 容量为$1$,费用为$0$ 的边(到终点不考虑油量)

求出最小费用最大流即可

代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch))  {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}

const int maxn = 200010;
const int inf  = 0x3f3f3f3f;

int n, m, s, t, ansflow;
int vis[maxn], d[maxn], p[maxn], a[maxn];
long long anscost;

struct Edge {
	int from, to, cap, flow, cost;
	Edge(int u, int v, int c, int f, int w): from(u), to(v), cap(c), flow(f), cost(w){}
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int u, int v, int c, int w) {
	edges.push_back(Edge(u, v, c, 0, w));
	edges.push_back(Edge(v, u, 0, 0,-w));
	int mm = edges.size();
	G[u].push_back(mm - 2);
	G[v].push_back(mm - 1);
}

bool BellmanFord(int& flow, long long& cost) {
    memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[s] = 0; vis[s] = 1; p[s] = 0; a[s] = inf;
	queue<int> Q;
	Q.push(s);
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		vis[x] = 0;
		for (int i = 0; i < G[x].size(); ++i) {
			Edge& e = edges[G[x][i]];
			if (e.cap > e.flow && d[e.to] > d[x] + e.cost) {
				d[e.to] = d[x] + e.cost;
				p[e.to] = G[x][i];
				a[e.to] = min(a[x], e.cap - e.flow);
				if (!vis[e.to]) {
					Q.push(e.to);
					vis[e.to] = 1;
				}
			}
		}
	}
	if (d[t] == inf) return false;
	flow += a[t];
	cost += (long long)d[t] * (long long)a[t];
	for (int u = t; u != s; u = edges[p[u]].from) {
		edges[p[u]].flow += a[t];
		edges[p[u] ^ 1].flow -= a[t];
	}
	return true;
}

int MinCostMaxFlow(long long& cost) {
	int flow = 0; cost = 0;
	while (BellmanFord(flow, cost));
	return flow;
}

int N, K, A, B, C;
int in[110][110];

int point(int x, int y, int dep) {
    return (x - 1) * N + y + dep * N * N;
}

int main() {
    N = read(); K = read(); A = read(); B = read(); C = read();
    s = 0; n = (K + 1) * N * N; t = n + 1;
    for (int i = 1; i <= N; ++i) 
        for (int j = 1; j <= N; ++j) {
            in[i][j] = read();
            if (in[i][j]) {
                for (int k = 1; k <= K; ++k) {
                    add(point(i, j, k), point(i, j, 0), 1, A);
                }
            }
            for (int k = 0; k < K; ++k) {
                if (in[i][j] && k) break;
                if (i + 1 <= N) add(point(i, j, k), point(i + 1, j, k + 1), 1, 0);
                if (j + 1 <= N) add(point(i, j, k), point(i, j + 1, k + 1), 1, 0);
                if (i - 1 >= 1) add(point(i, j, k), point(i - 1, j, k + 1), 1, B);
                if (j - 1 >= 1) add(point(i, j, k), point(i, j - 1, k + 1), 1, B);
            }
            if (!in[i][j]) add(point(i, j, K), point(i, j, 0), 1, A + C);
        }
    add(s, point(1, 1, 0), 1, 0);
    for (int k = 0; k <= K; ++k) {
        add(point(N, N, k), t, 1, 0);
    }
    ansflow = MinCostMaxFlow(anscost);
    printf("%lld\n", anscost);
    return 0;
}