最小割树小记

概要

最小割树是解决无向图上任意两点间最小割问题的工具。其核心思想为分治。

现在有一个图 \(G=(V,E)\) ，可以这样求得它的最小割树：

选取两个点 \(u,v\) ，求得这两个点之间的最小割。这个最小割将原图分为两部分 \(G_s\) 和 \(G_t\) 。任意 \(x\in G_s\) 和 \(y \in G_y\) 之间的最小割 至少 是 \(u,v\) 之间的最小割。

那么可以对于 \(G_s\) 和 \(G_y\) 分别递归。最后两个点之间的最小割就是在这个递归树上路径的最大值。

具体地，对于每一次递归，可以在求得最小割之后在新图上在 \(u,v\) 之间连一条权值为最小割的边。那么最后两个点之间的最小割就是树上路径上的最大边权。

如果使用 Dinic 求最小割的话，时间复杂度是 \(O(n^3m)\) 的。但一般认为是 \(O(能过)\) 。

模板

luogu4897

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

const int Maxn = 510;
const int Maxm = 1510;
const int INF = 2147483647;
const int MaxLog = 20;
int n, m, Q[ Maxn ], P[ Maxn ], q;
int Start[ Maxn ], Cur[ Maxn ], Next[ Maxm << 1 ], To[ Maxm << 1 ], Flow[ Maxm << 1 ], NowFlow[ Maxm << 1 ], Used;
int Start_[ Maxn ], Next_[ Maxn << 1 ], To_[ Maxn << 1 ], Val_[ Maxn << 1 ], Used_, D[ Maxn ][ MaxLog ][ 2 ], Deep_[ Maxn ];
int Deep[ Maxn ], Dis[ Maxn ], L, R, Queue[ Maxn ];

inline void AddEdge( int x, int y, int z ) {
    ++Used;
    Next[ Used ] = Start[ x ];
    To[ Used ] = y;
    Flow[ Used ] = z;
    Start[ x ] = Used;
    return;
}

inline void AddEdge_( int x, int y, int z ) {
    ++Used_;
    Next_[ Used_ ] = Start_[ x ];
    To_[ Used_ ] = y;
    Val_[ Used_ ] = z;
    Start_[ x ] = Used_;
    return;
}

bool Bfs( int S, int T ) {
    memset( Deep, 0, sizeof( Deep ) );
    memset( Dis, 0, sizeof( Dis ) );
    Deep[ S ] = 1;
    L = R = 0;
    Queue[ ++R ] = S;
    while( L < R ) {
        int u = Queue[ ++L ];
        for( int t = Start[ u ]; t != -1; t = Next[ t ] ) {
            int v = To[ t ];
            if( Deep[ v ] ) continue;
            if( NowFlow[ t ] <= 0 ) continue;
            Deep[ v ] = Deep[ u ] + 1;
            Queue[ ++R ] = v;
        }
    }
    return Deep[ T ];
}

int Dfs( int u, int Rest, int T ) {
    if( u == T || Rest <= 0 ) return Rest;
    int Ans = 0;
    for( int &t = Cur[ u ]; t != -1; t = Next[ t ] ) {
        int v = To[ t ];
        if( Deep[ v ] != Deep[ u ] + 1 ) continue;
        if( NowFlow[ t ] <= 0 ) continue;
        int d = Dfs( v, min( Rest, NowFlow[ t ] ), T );
        NowFlow[ t ] -= d; NowFlow[ t ^ 1 ] += d;
        Ans += d; Rest -= d;
        if( !Rest ) break;
    }
    return Ans;
}

int Dinic( int S, int T ) {
    int Ans = 0;
    memcpy( NowFlow, Flow, sizeof( Flow ) );
    while( Bfs( S, T ) ) {
        memcpy( Cur, Start, sizeof( Start ) );
        int d = Dfs( S, INF, T );
        while( d ) {
            Ans += d;
            d = Dfs( S, INF, T );
        }
    }
    return Ans;
}

void Build( int Left, int Right ) {
    if( Left >= Right ) return;
    int t = Dinic( Q[ Left ], Q[ Left + 1 ] );
    AddEdge_( Q[ Left ], Q[ Left + 1 ], t );
    Bfs( Q[ Left ], n + 1 );
    t =  Left - 1;
    for( int i = Left; i <= Right; ++i ) 
        if( Deep[ Q[ i ] ] )
            P[ ++t ] = Q[ i ];
    int Cut = t;
    for( int i = Left; i <= Right; ++i ) 
        if( !Deep[ Q[ i ] ] )
            P[ ++t ] = Q[ i ];
    for( int i = Left; i <= Right; ++i ) 
        Q[ i ] = P[ i ];
    Build( Left, Cut );
    Build( Cut + 1, Right );
    return;
}

void Build_( int u, int Fa, int c ) {
    D[ u ][ 0 ][ 0 ] = Fa;
    for( int i = 1; i < MaxLog; ++i ) D[ u ][ i ][ 0 ] = D[ D[ u ][ i - 1 ][ 0 ] ][ i - 1 ][ 0 ];
    D[ u ][ 0 ][ 1 ] = c;
    for( int i = 1; i < MaxLog; ++i ) D[ u ][ i ][ 1 ] = min( D[ u ][ i - 1 ][ 1 ], D[ D[ u ][ i - 1 ][ 0 ] ][ i - 1 ][ 1 ] );
    Deep_[ u ] = Deep_[ Fa ] + 1;
    for( int t = Start_[ u ]; t; t = Next_[ t ] ) {
        int v = To_[ t ];
        if( v == Fa ) continue;
        Build_( v, u, Val_[ t ] );
    }
    return;
}

int Query( int x, int y ) {
    int Ans = INF;
    if( Deep_[ x ] < Deep_[ y ] ) swap( x, y );
    for( int i = MaxLog - 1; i >= 0; --i )
        if( Deep_[ D[ x ][ i ][ 0 ] ] >= Deep_[ y ] ) {
            Ans = min( Ans, D[ x ][ i ][ 1 ] );
            x = D[ x ][ i ][ 0 ];
        }
    if( x == y ) return Ans;
    for( int i = MaxLog - 1; i >= 0; --i ) 
        if( D[ x ][ i ][ 0 ] != D[ y ][ i ][ 0 ] ) {
            Ans = min( Ans, D[ x ][ i ][ 1 ] );
            Ans = min( Ans, D[ y ][ i ][ 1 ] );
            x = D[ x ][ i ][ 0 ];
            y = D[ y ][ i ][ 0 ];
        }
    Ans = min( Ans, D[ x ][ 0 ][ 1 ] );
    Ans = min( Ans, D[ y ][ 0 ][ 1 ] );
    return Ans;
}

int main() {
    Used = -1;
    memset( Start, 255, sizeof( Start ) );
    scanf( "%d%d", &n, &m );
    for( int i = 1; i <= m; ++i ) {
        int x, y, z;
        scanf( "%d%d%d", &x, &y, &z );
        AddEdge( x, y, z );
        AddEdge( y, x, z );
    }
    for( int i = 0; i <= n; ++i ) Q[ i ] = i;
    Build( 0, n );
    Build_( 0, 0, INF );
    scanf( "%d", &q );
    for( int i = 1; i <= q; ++i ) {
        int x, y;
        scanf( "%d%d", &x, &y );
        printf( "%d\n", Query( x, y ) );
    }
    return 0;
}

最小割树小记

原文：https://www.cnblogs.com/chy-2003/p/11815124.html