【openjudge】C15C Rabbit's Festival【CDQ分治+并查集】

缺乏、安全感 2022-08-05 00:56 120阅读 0赞

传送门：[【openjudge】C15C Rabbit’s Festival][openjudge_C15C Rabbit_s Festival]

题目分析：

考虑到每条边最多只断一天，我们可以用cdq来模拟这个过程。假设当前区间为\[l,r\]，令m=(l\+r)/2，选择\[l,m\]区间时，我们便将\[m\+1,r\]内的边全部使用掉，然后递归处理\[l,m\]部分。处理完\[l,m\]部分后我们将\[m\+1,r\]回溯掉，然后将\[l,m\]内的边都使用掉，递归处理\[m\+1,r\]部分，最后再将\[l,m\]内使用的边回溯掉……

YY一下，我们可以发现这个过程正好模拟了并查集的加边过程（利用了逐层并差集的方法）。

最后我们发现每个区间我们恰好用了一次，一共log  ( K )层，所以一共我们使用了O ( K log  ( K ) )个元素，接下来我们考虑里面的并查集，为了保证并查集的复杂度，我们考虑启发式合并，高度小的合并到高度大的上面。这里我们假设是一个 log ，那么算法总复杂度为O ( K log2  ( K ) )。

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std ;
    
    typedef long long LL ;
    
    #define clr( a , x ) memset ( a , x , sizeof a )
    #define cpy( a , x ) memcpy ( a , x , sizeof a )
    
    const int MAXN = 100005 ;
    const int MAXE = 200005 ;
    
    struct Edge {
        int u , v , n ;
        Edge () {}
        Edge ( int u , int v , int n ) : u ( u ) , v ( v ) , n ( n ) {}
    } ;
    
    struct Node {
        int u , v , cntu , cntv , ranku , rankv ;
        Node () {}
        Node ( int u , int v , int cntu , int cntv , int ranku , int rankv ) : u ( u ) , v ( v ) , cntu ( cntu ) , cntv ( cntv ) , ranku ( ranku ) , rankv ( rankv ) {}
    } ;
    
    Edge E[MAXE] ;
    int H[MAXN] , cntE ;
    int n , m , k ;
    Node S[MAXE] ;
    int cnt[MAXN] ;
    int p[MAXN] ;
    int rank[MAXN] ;
    int top ;
    LL ans ;
    
    void init () {
        ans = 0 ;
        top = 0 ;
        cntE = 0 ;
        clr ( H , -1 ) ;
    }
    
    void addedge ( int x , int u , int v ) {
        E[cntE] = Edge ( u , v , H[x] ) ;
        H[x] = cntE ++ ;
    }
    
    int find ( int x ) {
        int o = x ;
        while ( p[o] != o ) o = p[o] ;
        int ans = o ;
        while ( p[x] != x ) {
            int tmp = p[x] ;
            p[x] = tmp ;
            x = tmp ;
        }
        return ans ;
    }
    
    void Union ( int l , int r ) {
        for ( int t = l ; t <= r ; ++ t ) {
            for ( int i = H[t] ; ~i ; i = E[i].n ) {
                int u = find ( E[i].u ) ;
                int v = find ( E[i].v ) ;
                if ( u == v ) continue ;
                S[top ++] = Node ( u , v , cnt[u] , cnt[v] , rank[u] , rank[v] ) ;
                ans += ( LL ) cnt[u] * cnt[v] ;
                if ( rank[u] <= rank[v] ) {
                    rank[v] = max ( rank[v] , rank[u] + 1 ) ;
                    p[u] = v ;
                    cnt[v] += cnt[u] ;
                } else {
                    p[v] = u ;
                    cnt[u] += cnt[v] ;
                }
            }
        }
    }
    
    void back ( int x ) {
        while ( top > x ) {
            -- top ;
            int u = S[top].u , v = S[top].v ;
            ans -= ( LL ) S[top].cntu * S[top].cntv ;
            p[u] = u ;
            p[v] = v ;
            cnt[u] = S[top].cntu ;
            cnt[v] = S[top].cntv ;
            rank[u] = S[top].ranku ;
            rank[v] = S[top].rankv ;
        }
    }
    
    void cdq ( int l , int r ) {
        if ( l == r ) {
            printf ( "%lld\n" , ans ) ;
            return ;
        }
        int m = ( l + r ) >> 1 ;
        int rtop = top ;
        Union ( m + 1 , r ) ;
        cdq ( l , m ) ;
        back ( rtop ) ;
        Union ( l , m ) ;
        cdq ( m + 1 , r ) ;
        back ( rtop ) ;
    }
    
    void solve () {
        int u , v , c ;
        init () ;
        for ( int i = 1 ; i <= n ; ++ i ) {
            p[i] = i ;
            cnt[i] = 1 ;
            rank[i] = 0 ;
        }
        for ( int i = 0 ; i < m ; ++ i ) {
            scanf ( "%d%d%d" , &u , &v , &c ) ;
            if ( c > k ) {
                u = find ( u ) ;
                v = find ( v ) ;
                if ( u == v ) continue ;
                if ( rank[u] <= rank[v] ) {
                    rank[v] = max ( rank[v] , rank[u] + 1 ) ;
                    p[u] = v ;
                    cnt[v] += cnt[u] ;
                } else {
                    p[v] = u ;
                    cnt[u] += cnt[v] ;
                }
            } else addedge ( c , u , v ) ;
        }
        cdq ( 1 , k ) ;
    }
    
    int main () {
        while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;
        return 0 ;
    }

[openjudge_C15C Rabbit_s Festival]: http://poj.openjudge.cn/practice/C15C/