BZOJ-1196: [HNOI2006]公路修建问题（二分）

题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1196

没什么好说的，二分判定最大值，然后并查集判断连通性就好了。（之前用Kruskal弄了半版WA的我真是傻X）

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 10010
#define MAXM 20010
 
int s[ MAXM ] , t[ MAXM ] , c1[ MAXM ] , c2[ MAXM ] , n , m , k ;
 
struct Uset {
 
    int father[ MAXN ] ;
 
    void Init(  ) {
        memset( father , 0 , sizeof( father ) ) ;
    }
 
    int Find( int x ) {
        int i = x , j = x ;
        for ( ; father[ i ] ; i = father[ i ] ) ;
        for ( ; father[ j ] ; ) {
            int k = father[ j ] ;
            father[ j ] = i ; 
            j = k ;
        }
        return i ;
    }
 
    bool check( int x , int y ) {
        return Find( x ) == Find( y ) ;
    }
 
    void Union( int x , int y ) {
        father[ Find( x ) ] = Find( y ) ;
    }
 
} u ;
 
bool Check( int x ) {
    u.Init(  ) ; 
    int cnt = 0 ; 
    for ( int i = 0 ; i ++ < m ; ) if ( ! u.check( s[ i ] , t[ i ] ) && c1[ i ] <= x ) {
        ++ cnt , u.Union( s[ i ] , t[ i ] ) ;
    }
    if ( cnt < k ) return false ;
    for ( int i = 0 ; i ++ < m ; ) if ( ! u.check( s[ i ] , t[ i ] ) && c2[ i ] <= x ) {
        u.Union( s[ i ] , t[ i ] ) , ++ cnt ;
    }
    for ( int i = 1 ; i ++ < n ; ) if ( ! u.check( i , i - 1 ) ) return false ;
    return true ;
}
 
int main(  ) {
    scanf( "%d%d%d" , &n , &k , &m ) ; -- m ;
    for ( int i = 0 ; i ++ < m ; ) scanf( "%d%d%d%d" , s + i , t + i , c1 + i , c2 + i ) ;
    int l = 0 , r = 30000 ;
    while ( r - l > 1 ) {
        int mid = ( l + r ) >> 1 ; 
        if ( Check( mid ) ) r = mid ; else l = mid ;
    }
    printf( "%d\n" , r ) ;
    return 0 ; 
}