汽車加油行駛問題(洛谷P4009 分層圖費用流)

第一次見到分層思想和網絡流聯系起來的題,淺錄一下

題目連結: P4009 汽車加油行駛問題

該題方法很多,但是網絡流應該是最能接受和了解的吧 (

由于汽油的影響,建圖變得不那麼容易,正常建圖又無法将位置和油量結合起來,是以考慮分層建圖

我們定義狀态 ( i , j , k ) (i,j,k) (i,j,k)代表走到點 ( i , j ) (i,j) (i,j)時剩餘油量為 k k k.

• 建立源點 S S S和彙點 T T T

  S ⇒ ( 1 , 1 , K ) S \Rightarrow (1,1,K) S⇒(1,1,K)連容量為 1 1 1,費用為 0 0 0的邊

  因為不确定到達終點時剩餘油量的多少

  ( n , n , 0 ∽ K ) ⇒ T (n,n,0 \backsim K) \Rightarrow T (n,n,0∽K)⇒T連容量為1,費用為 0 0 0的邊

• 對于已經放置加油站的點

  由于是強制消費(嗚嗚),是以無論來之前是多少油都得加滿

  ( i , j , 0 ∽ K − 1 ) ⇒ ( i , j , K ) (i,j,0 \backsim K-1) \Rightarrow (i,j,K) (i,j,0∽K−1)⇒(i,j,K)連容量為 1 1 1,費用為 A A A的邊

  此時已經為滿油狀态

  ( i , j , K ) (i,j,K) (i,j,K)向下一層的 ( i − 1 , j ) (i-1,j) (i−1,j)以及 ( i , j − 1 ) (i,j-1) (i,j−1)連容量為 1 1 1,費用為 B B B的邊

  ( i , j , K ) (i,j,K) (i,j,K)向下一層的 ( i + 1 , j ) (i+1,j) (i+1,j)以及 ( i , j + 1 ) (i,j+1) (i,j+1)連容量為 1 1 1,費用為 0 0 0的邊

• 對于沒有放置加油站的點

  首先要明确一個問題,什麼時候必須放置加油站,情況隻有一個:走到沒加油站的位置并且沒油了

  ( i , j , 0 ) ⇒ ( i , j , K ) (i,j,0) \Rightarrow (i,j,K) (i,j,0)⇒(i,j,K)連容量為 1 1 1,費用為 A + C A+C A+C的邊

  ( i , j , 1 ∽ K ) (i,j,1 \backsim K) (i,j,1∽K)向下一層的 ( i − 1 , j ) (i-1,j) (i−1,j)以及 ( i , j − 1 ) (i,j-1) (i,j−1)連容量為 1 1 1,費用為 B B B的邊

  ( i , j , 1 ∽ K ) (i,j,1 \backsim K) (i,j,1∽K)向下一層的 ( i + 1 , j ) (i+1,j) (i+1,j)以及 ( i , j + 1 ) (i,j+1) (i,j+1)連容量為 1 1 1,費用為 0 0 0的邊

最大流對應下的最小費用即為所求

#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;
}