第一次见到分层思想和网络流联系起来的题,浅录一下

题目链接: P4009 汽车加油行驶问题

该题方法很多,但是网络流应该是最能接受和理解的吧 (

由于汽油的影响,建图变得不那么容易,常规建图又无法将位置和油量结合起来,所以考虑分层建图

我们定义状态$(i,j,k)$代表走到点$(i,j)$时剩余油量为$k$.

  • 建立源点S和汇点T

    $S \Rightarrow (1,1,K)$ 连容量为1,费用为0的边

    因为不确定到达终点时剩余油量的多少

    $(n,n,0 \backsim K) \Rightarrow T$连容量为1,费用为0的边

  • 对于已经放置加油站的点

    由于是强制消费(呜呜),所以无论来之前是多少油都得加满

    $(i,j,0 \backsim K-1) \Rightarrow (i,j,K)$连容量为1,费用为A的边

    此时已经为满油状态

    $(i,j,K)$向下一层的$(i-1,j)$以及$(i,j-1)$连容量为1,费用为B的边

    $(i,j,K)$向下一层的$(i+1,j)$以及$(i,j+1)$连容量为1,费用为0的边

  • 对于没有放置加油站的点

    首先要明确一个问题,什么时候必须放置加油站,情况只有一个:走到没加油站的位置并且没油了

    $(i,j,0) \Rightarrow (i,j,K)$连容量为1,费用为A+C的边

    $(i,j,1 \backsim K)$向下一层的$(i-1,j)$以及$(i,j-1)$连容量为1,费用为B的边

    $(i,j,1 \backsim K)$向下一层的$(i+1,j)$以及$(i,j+1)$连容量为1,费用为0的边

最大流对应下的最小费用即为所求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5, INF = 0x3f3f3f3f;
struct Edge {
    int from, to, flow, cost;

    Edge(int from, int to, int flow, int cost) : from(from), to(to), flow(flow), cost(cost) {}
};
struct Dinic {
    int S, T, m; 
    int d[N], incf[N], pre[N];
    bool vis[N];
    vector< Edge > edges;
    vector< int > G[N];

    Dinic(int S, int T) : S(S), T(T) {}

    void AddEdge(int from, int to, int flow, int cost) {
        edges.push_back(Edge(from, to, flow, cost));
        edges.push_back(Edge(to, from, 0, -cost));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool SPFA() {
        memset(d, 0x3f, sizeof d);
        memset(incf, 0, sizeof incf);
        memset(vis, false, sizeof vis);
        queue<int> Q;
        Q.push(S);
        vis[S] = true, incf[S] = INF, d[S] = 0;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = false;
            for (int i = 0; i < G[x].size(); ++ i) {
                Edge &e = edges[G[x][i]];
                if (d[x] + e.cost < d[e.to] && e.flow) {
                    d[e.to] = d[x] + e.cost;
                    pre[e.to] = G[x][i];
                    incf[e.to] = min(incf[x], e.flow);
                    if (!vis[e.to]) {
                        vis[e.to] = true;
                        Q.push(e.to);
                     }
                }
            }
        }
        return d[T] != INF;
    }

    pair< int, int > MCMF() {
        int maxflow = 0, mincost = 0;
        while (SPFA()) {
            maxflow += incf[T];
            mincost += incf[T] * d[T];
            for (int i = T; i != S; i = edges[pre[i] ^ 1].to) {
                edges[pre[i]].flow -= incf[T];
                edges[pre[i] ^ 1].flow += incf[T];
            }
        }
        return {maxflow, mincost};
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);  

    int n, K, A, B, C;
    cin >> n >> K >> A >> B >> C;

    auto get = [&] (int i, int j, int k) { return k * n * n + (i - 1) * n + j;};

    auto f = [&] (int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= n;};


    //0~k层代表i格油
    Dinic d(0, (K + 1) * n * n + 1);
    d.AddEdge(d.S, get(1, 1, K), 1, 0);
    for (int k = 0; k <= K; ++ k) 
        d.AddEdge(get(n, n, k), d.T, 1, 0);

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1, x; j <= n; ++ j) {
            cin >> x;
            if (x) {
                // 非满油状态向满油状态连边
                for (int k = 0; k < K; ++ k) 
                    d.AddEdge(get(i, j, k), get(i, j, K), 1, A);
                // 满油向下一层相邻点连边
                if (f(i - 1, j))
                    d.AddEdge(get(i, j, K), get(i - 1, j, K - 1), 1, B);
                if (f(i, j - 1))
                    d.AddEdge(get(i, j, K), get(i, j - 1, K - 1), 1, B);
                if (f(i + 1, j))
                    d.AddEdge(get(i, j, K), get(i + 1, j, K - 1), 1, 0);
                if (f(i, j + 1))
                    d.AddEdge(get(i, j, K), get(i, j + 1, K - 1), 1, 0);
            } else {
                // 向相邻点连边
                for (int k = K; k >= 1; -- k) {
                    if (f(i - 1, j))
                        d.AddEdge(get(i, j, k), get(i - 1, j, k - 1), 1, B);
                    if (f(i, j - 1))
                        d.AddEdge(get(i, j, k), get(i, j - 1, k - 1), 1, B);
                    if (f(i + 1, j))
                        d.AddEdge(get(i, j, k), get(i + 1, j, k - 1), 1, 0);
                    if (f(i, j + 1))
                        d.AddEdge(get(i, j, k), get(i, j + 1, k - 1), 1, 0);
                }
                // *只有遇到没油且没加油站的时候,才会放置加油站并且加油
                d.AddEdge(get(i, j, 0), get(i, j, K), 1, A + C);
            }
        }
    } 
    cout << d.MCMF().second << '\n';
    return 0;
}