题目链接

过程

暴力跑最小割显然会 TLE，于是引出了最小割树。

对于一个图，随机两个点 $u, v$，求从 $u$ 到 $v$ 的最小割，按照割边将图分成两部分，

删除所有割边，取而代之的是在最小割树上连接边 $(u, v)$，边权为最小割的容量，并分别对 $u,v$ 所在的连通图求最小割树。

最终以 $O(n^3m)$ 的复杂度求得了最小割树，任意两点的最小割即为树上简单路径边权最小值，证明不会。

代码

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

const int N = 510, M = 10010, inf = 0x3f3f3f3f;

int n, m, S, T;
int v[N], t[N];
int h[N], h2[N], e[M], c[M], ne[M], idx, pidx;
int q[N], dep[N], cur[N];

void add_edge(int u, int v, int w) {
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

void add2(int u, int v, int w) {
    e[idx] = v, c[idx] = w, ne[idx] = h2[u], h2[u] = idx ++ ;
}

bool bfs() {
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dep[j] == -1 && c[i]) {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i]) {
            int t = find(j, min(c[i], limit - flow));
            if (!t) dep[j] = -2;
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    for (int i = 0; i < pidx; i += 2) c[i] += c[i ^ 1], c[i ^ 1] = 0;
    int res = 0, flow;
    while (bfs()) while (flow = find(S, inf)) res += flow;
    return res;
}

void build(int l, int r) {
    if (l >= r) return;
    S = v[l], T = v[l + 1];
    int ans = dinic();
    add2(S, T, ans);
    add2(T, S, ans);
    int t1 = l, t2 = r;
    for (int i = l; i <= r; i ++ )
        if (dep[v[i]] != -1) t[t1 ++ ] = v[i];
        else t[t2 -- ] = v[i];
    for (int i = l; i <= r; i ++ ) v[i] = t[i];
    build(l, t1 - 1), build(t1, r);
}

int dfs(int u, int fa, int v) {
    for (int i = h2[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        if (ver == v) return c[i];
        int tmp = dfs(ver, u, v);
        if (tmp != -1) return min(tmp, c[i]);
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    n ++ ;
    memset(h, -1, sizeof h);
    memset(h2, -1, sizeof h2);
    for (int i = 1; i <= m; i ++ ) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u ++ , v ++ ;
        add_edge(u, v, w), add_edge(v, u, w);
    }
    pidx = idx;
    for (int i = 1; i <= n; i ++ ) v[i] = i;
    build(1, n);
    int Q;
    scanf("%d", &Q);
    while (Q -- ) {
        int u, v;
        scanf("%d%d", &u, &v);
        u ++ , v ++ ;
        printf("%d\n", dfs(u, -1, v));
    }
    return 0;
}