[Problem]\color{green}{\texttt{[Problem]}}[Problem]给定一个nnn个点mmm条边的无向图，求出一个至少有333个点的环，使得环上的
[Problem] [Problem] 给定一个 n n n m m m 至少 有 3 3 3 No solution.（注意，. 是必须的）。 1 ≤ n ≤ 100 , 1 ≤ m ≤ 5 × 1 0 3 1 \leq n \leq 100,1 \leq m \leq 5 \times 10^3 1 ≤ n ≤ 1 0 0 , 1 ≤ m ≤ 5 × 1 0 3 记 d d d 1 ≤ d ≤ 1 × 1 0 5 1\leq d \leq 1 \times 10^5 1 ≤ d ≤ 1 × 1 0 5 [Part one] \color{blue}{\texttt{[Part one]}} [Part one] Floyd 的本质是什么？
对于很多人（包括一年前的笔者）而言，Floyd 算法就是：
for ( int k= 1 ; k<= n; k++ ) for ( int i= 1 ; i<= n; i++ ) for ( int j= 1 ; j<= n; j++ ) f[ i] [ j] = min ( f[ i] [ j] , f[ i] [ k] + f[ k] [ j] ) ;
这样一个 O ( n 3 ) O\left (n^3\right) O ( n 3 )
但是为什么 Floyd 算法是对的呢？这就涉及它的核心。
原始的 Floyd 是这样的：记 f k , i , j f_{k,i,j} f k , i , j i i i j j j 1 − k 1-k 1 − k 中转点 的最短路长度。什么是中转点，就是最短路径 ( i , j ) (i,j) ( i , j ) i i i j j j
于是我们有如下的转移方程：
f k , i , j = min 1 ≤ l ≤ k − 1 { f k − 1 , i , k + f k − 1 , k , j } f_{k,i,j}=\min\limits_{1 \leq l \leq k-1}\left \{f_{k-1,i,k}+f_{k-1,k,j}\right \} f k , i , j = 1 ≤ l ≤ k − 1 min { f k − 1 , i , k + f k − 1 , k , j }
它的意义是先只用 1 1 1 l l l i i i k k k 1 1 1 l l l k k k j j j
于是我们可以用滚动数组优化它，就得到了我们上面的代码（顺便一提，正是因为我们用了滚动数组，所以 k k k
[Part two] \color{blue}{\texttt{[Part two]}} [Part two]
讲了这么多，它和原题有什么关系呢？
我们假设这个环上有一条边 ( i , j ) (i,j) ( i , j ) i i i j j j
有什么用？我们随便找两个点 i i i j j j 1 1 1 k − 1 k-1 k − 1 T i , j , k − 1 T_{i,j,k-1} T i , j , k − 1 f f f i i i k k k k k k j j j
所以，最小的环的权值（就是换上所有边的权值总和）ans \texttt{ans} ans
ans = min i , j , k ∈ { 1.. n } { T k − 1 , i , j + a i , k + a k , j } \texttt{ans}=\min\limits_{i,j,k \in \left \{ 1..n \right \} } \left \{ T_{k-1,i,j}+a_{i,k}+a_{k,j} \right \} ans = i , j , k ∈ { 1 . . n } min { T k − 1 , i , j + a i , k + a k , j }
a i , j a_{i,j} a i , j ( i , j ) (i,j) ( i , j )
注意，图上必须要有边 ( i , k ) (i,k) ( i , k ) ( k , j ) (k,j) ( k , j )
[code] \color{blue}{\texttt{[code]}} [code]
typedef long long ll; const ll inf= 0x3f3f3f3f3f3f ; [ 110 ] [ 110 ] , f[ 110 ] [ 110 ] , n, m, ans; inline void ckmin ( ll & a, ll b) { a= min ( a, b) ; } int main ( ) { scanf ( "%lld%lld" , & n, & m) ; for ( int i= 1 ; i<= n; i++ ) for ( int j= 1 ; j<= n; j++ ) f[ i] [ j] = a[ i] [ j] = inf; for ( int i= 1 , u, v, w; i<= m; i++ ) { scanf ( "%d%d%d" , & u, & v, & w) ; ckmin ( a[ u] [ v] , w) ; ckmin ( a[ v] [ u] , w) ; ckmin ( f[ u] [ v] , w) ; ckmin ( f[ v] [ u] , w) ; } ans= inf; for ( int k= 1 ; k<= n; k++ ) { for ( int i= 1 ; i< k; i++ ) for ( int j= i+ 1 ; j< k; j++ ) ckmin ( ans, f[ i] [ j] + a[ i] [ k] + a[ k] [ j] ) ; for ( int i= 1 ; i<= n; i++ ) if ( i!= k&& f[ i] [ k] != inf) for ( int j= 1 ; j<= n; j++ ) if ( j!= i&& j!= k&& f[ k] [ j] != inf) ckmin ( f[ i] [ j] , f[ i] [ k] + f[ k] [ j] ) ; } if ( ans!= inf) printf ( "%lld" , ans) ; else printf ( "No solution." ) ; return 0 ; } 洛谷的P6175就是模板哦。
京公网安备 11010802041100号