目标
解决问题「CQOI2016」不同的最小割。
算法介绍
最小割树用于解决一类多点之间最小割的问题。luogu上的题：【模板】最小割树（Gomory-Hu Tree）。然后我们借助这道模板题来看看如何实现。
首先我们选择两个点$x$和$y$，求出它们的最小割。它们的最小割把点集分成了两个部分$U$和$V$。然后对于任意$x’\in U$和$y’\in V$，都有$x’$与$y’$之间的最小割不大于$x$和$y$之间的最小割（反证法易证）。这样我们可以在$U$和$V$之间连一条权值为$x$到$y$最小割的边，然后对集合$U$和$V$分别进行类似操作，我们就得到了一棵最小割树。容易发现两个点之间的最小割就是它们树上简单路径上权值最小边的权值。
复杂度分析
我们发现每次连一条边，都需要求一次最小割。而边总共有$n-1$条。如果使用$Dinic$或$ISAP$，那么理论时间复杂度上限为$O(n^3m)$。可以无视，谁叫它的上界那么松。同样的，如果使用$HLPP$，那么理论上限就是$O(n^3\sqrt m)$。但是对于随机数据，ISAP的表现远好于HLPP。
解决目标的最后一步
前面提到，两个点之间的最小割就是它们树上简单路径上权值最小边的权值，那么对于模板题，只需要再套一层倍增即可。而对于目标题我们甚至不需要把树建出来，只需要统计不同的边权即可。
参考代码（【模板】最小割树（Gomory-Hu Tree））
#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;
}
参考代码（「CQOI2016」不同的最小割）
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 860;
const int Maxm = 8510;
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 Deep[ Maxn ], Dis[ Maxn ], L, R, Queue[ Maxn ];
map< int, int > Map;
int Ans;
inline void AddEdge( int x, int y, int z ) {
++Used;
Next[ Used ] = Start[ x ];
To[ Used ] = y;
Flow[ 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 ] );
if( Map.find( t ) == Map.end() ) {
++Ans;
Map[ t ] = 1;
}
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;
}
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 = 1; i <= n; ++i ) Q[ i ] = i;
Build( 1, n );
printf( "%d\n", Ans );
return 0;
}
