P1135 奇怪的电梯

P1135 奇怪的电梯 题解。

首先这种简单最短路的题，首先是建图然后再是最短路，我们伟大的费用流正好可以解决这一类的问题，这道题你只需要 $i$ 分别向 $i \pm K_i$ 连 $(1, 1)$ 的边然后跑最小费用最大流就可以轻松解决这个问题了。

但是这道题有一点不一样，直接跑可能流量大于 $1$，但是最短路是只能有一条的，可恶的最短路，可惜就算你路径有几条我伟大的费用流也能跑出正确最短路，怎么做呢？

我们只需要建一个新的汇点 $B'$ 然后 $B$ 向 $B'$ 连 $(1, 0)$ 的边，而最短路只能有一条？根本不在乎，我们直接这样连边，流量就不超过 $1$ 了，这样做就是对的，这世间，还有什么能够阻挡！！！！！还有什么能够阻挡我们的费用流算法！！！！！！！！！

时间复杂度 $O(n^3)$，可能还有一点小常数不过没有人在乎，这就是网络流算法的魅力，BFS 这种逆时代浪潮的做法迟早被淹没在费用流恐怖的实力之下！！！

大概就是上面这样。

                
#include <bit>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
using u32 = unsigned;
using p32 = pair<int, int>;
const int N = 205, M = 405, INF = 0x3f3f3f3f;
int n, s, t, tt, a[N], h[N], dis[N], pos[N], siz[35], cur[N], head[N],
    cnt = 1, beg, top, flow, cost;
bool vis[N];
struct edge {
    int to, nex, w, c;
} e[M << 1];
queue<int> Q;
vector<int> buc[35], tmp;
void add(int u, int v, int w, int c) { e[++cnt] = {v, head[u], w, c}, head[u] = cnt; }
void addflow(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
void spfa() {
    memset(h, 0x3f, sizeof(h));
    h[s] = 0, vis[s] = true, Q.push(s);
    while (!Q.empty()) {
        int u = Q.front();
        vis[u] = false, Q.pop();
        for (int i = head[u]; i; i = e[i].nex) {
            int v = e[i].to, w = e[i].w, c = e[i].c;
            if (h[v] > h[u] + c && w) {
                h[v] = h[u] + c;
                if (!vis[v]) vis[v] = true, Q.push(v);
            }
        }
    }
}
// radix heap
void insert(int x) {
    int k = bit_width<u32>(dis[x] ^ dis[top]);
    ++siz[k], pos[x] = buc[k].size(), buc[k].push_back(x);
}
void update(int x, int y) {
    int k = bit_width<u32>(dis[x] ^ dis[top]);
    --siz[k], dis[x] = y, insert(x);
}
void removemin() {
    pos[top] = -1, --siz[0];
    if (siz[0]) {
        while (pos[top = buc[0][beg]] == -1) ++beg;
        return;
    }
    int cur = 0, las = top;
    for (int i = 30; i >= 1; i--)
        if (siz[i]) cur = i;
    siz[cur] = beg = top = 0, tmp = move(buc[cur]);
    for (int i = 0; i <= cur; i++) buc[i].clear();
    for (int i = 0; i < (int)tmp.size(); i++) {
        int k = bit_width<u32>(dis[tmp[i]] ^ dis[las]);
        if (k == cur && pos[tmp[i]] == i && dis[tmp[i]] < dis[top]) top = tmp[i];
    }
    for (int i = 0; i < (int)tmp.size(); i++) {
        int k = bit_width<u32>(dis[tmp[i]] ^ dis[las]);
        if (k == cur && pos[tmp[i]] == i) insert(tmp[i]);
    }
}
bool dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[top = s] = beg = 0;
    for (int i = 0; i <= 30; i++) siz[i] = 0, buc[i].clear();
    for (int i = 1; i <= n + 1; i++) insert(i);
    for (int i = 1; i <= n + 1; i++, removemin()) {
        if (dis[top] == INF) break;
        for (int j = head[top]; j; j = e[j].nex) {
            int v = e[j].to, w = e[j].w, c = e[j].c;
            if (dis[v] > dis[top] + c + h[top] - h[v] && w)
                update(v, dis[top] + c + h[top] - h[v]);
        }
    }
    return dis[t] != INF;
}
int dfs(int u, int flow) {
    if (u == t) return flow;
    int used = 0;
    vis[u] = true;
    for (int &i = cur[u]; i; i = e[i].nex) {
        int v = e[i].to, w = e[i].w, c = e[i].c;
        if (!vis[v] && dis[v] == dis[u] + c + h[u] - h[v] && w) {
            int ret = dfs(v, min(flow - used, w));
            used += ret, e[i].w -= ret, e[i ^ 1].w += ret;
            if (used == flow) break;
        }
    }
    vis[u] = false;
    return used;
}
void dinic() {
    int ret;
    spfa();
    while (dijkstra()) {
        memcpy(cur, head, sizeof(cur));
        memset(vis, 0, sizeof(vis));
        while ((ret = dfs(s, INF))) flow += ret, cost += ret * (dis[t] + h[t]);
        for (int i = 1; i <= n + 1; i++) h[i] += dis[i];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s >> tt, t = n + 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i - a[i] >= 1) addflow(i, i - a[i], 1, 1);
        if (i + a[i] <= n) addflow(i, i + a[i], 1, 1);
    }
    addflow(tt, t, 1, 0);
    dinic();
    if (flow == 1) cout << cost;
    else cout << "-1";
    return 0;
}
                
cpp