神人题解

Manki23333333 · 2025-08-23 17:37:59 · 题解

这显然是最大流板子题，所以我们用最大流解决问题。

题解流程

给每个点编号，同时分配一个虚拟源点。

给源点向每一个点建容量为 1 的边，同时对于每个点，对它一步能走到的点建容量为 +\infty 的边。

最后从源点到最后一个点跑最大流即可。

正确性

显然一个点最多只会贡献 1 的答案。

如果一个点可以被贡献答案，那么肯定是走过了又走出去了若干次，这与网络流是一致的。

如果一个点不可以被贡献答案，那么就无法流量守恒，最大流不会选择增广它。

代码（赛时）

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

const int inf = 1e9;

namespace MFlow {
    const int N = 1e5;
    const int M = 2e5;  
    struct Edge {
        int to, w, nxt, ansid;
    } edges [M + 5];

    int m, ecnt = 1, head [N + 5], cur [N + 5], dep [N + 5], ans [N + 5];
    void add (int u, int v, int w, int ansid = 0) {
        ecnt ++;
        edges [ecnt] = {v, w, head [u], ansid};
        head [u] = ecnt;

        ecnt ++;
        edges [ecnt] = {u, 0, head [v]};
        head [v] = ecnt;
    }

    queue <int> q;
    bool bfs (int s, int t) {
        memset (dep, 0, sizeof dep);
        dep [s] = 1;
        while (!q. empty ()) q. pop ();
        q. push (s);
        while (!q. empty ()) {
            int u = q. front (); q. pop ();
            for (int ei = head [u] ; ei ; ei = edges [ei]. nxt) {
                auto &e = edges [ei];
                if (!dep [e. to] && e. w) {
                    dep [e. to] = dep [u] + 1;
                    q. push (e. to);
                    if (e. to == t) return 1;
                }
            }
        }
        return 0;
    }

    int dfs (int u, int t, int flow) {
        if (u == t) return flow;
        int sum = 0;
        for (int e = cur [u] ; e ; e = edges [e]. nxt) {
            cur [u] = e;
            int to = edges [e]. to;
            if (edges [e]. w && dep [to] == dep [u] + 1) {
                int f = dfs (to, t, min (flow, edges [e]. w));
                edges [e]. w -= f;
                edges [e ^ 1]. w += f;
                sum += f;
                flow -= f;
                if (!flow) break;
            }
        }
        if (!sum) dep [u] = 0;
        return sum;
    }

    int dinic (int s, int t, int n) {
        int flow = 0;
        while (bfs (s, t)) {
            for (int i = 1 ; i <= n ; i ++) cur [i] = head [i];
            flow += dfs (s, t, inf);
        }
        return flow;
    }

    int* count_ans () {
        for (int i = 1 ; i <= ecnt ; i ++)  {
            if (edges [i]. ansid) {
                ans [edges [i]. ansid] += edges [i]. w;
            }
        }
        return ans; 
    } 

    void clear () {
        ecnt = 1;
        memset (head, 0, sizeof head);
        memset (ans, 0, sizeof ans);
    }
};

using MFlow :: add;
using MFlow :: dinic;
int n, m, ids [105] [105], a [105];
void Turn () {
    cin >> n;
    m = 1;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a [i];
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= a [i] ; j ++) {
            ids [i] [j] = ++ m;
            add (1, ids [i] [j], 1);
        }
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= a [i] ; j ++) {
            if (ids [i] [j - 1])
                add (ids [i] [j - 1], ids [i] [j], inf);
            if (ids [i - 1] [j])
                add (ids [i - 1] [j], ids [i] [j], inf);
            if (ids [i + 1] [j])
                add (ids [i + 1] [j], ids [i] [j], inf);
        }
    }
    cout << dinic (1, ids [n] [a [n]], m);
}

int _; void Init () {
//  ios :: sync_with_stdio (0); cin. tie (0); cout. tie (0); 
    _ = 1;
//  freopen (".in", "r", stdin);
//  freopen (".out", "w", stdout);
//  cin >> _;
}

    signed main () { Init ();
    while (_ --> 0)
    Turn (); return 0; }