CFR 742 D. Arpa's weak amphitheater and Mehrdad's valuable Hoses ( DP, Knapsack, Union Find )
題意:
給每個人的重量和權值。再給每對朋友的關係。x 和 y 屬於同個朋友圈,若存在一個序列 a[ 0 ], a[ 1 ], .. a[ i ],滿足所有相鄰的人都是朋友。對於每個朋友圈,可以選一個人,或選所有的人,或都不選,邀請到派對。但是派對最多只能容下總重量 W。求可能達成的最大總權值。
資料規模:
人數 1 ≤ N≤ 1000
容量 1 ≤ W ≤ 1000
人的重量 1 ≤ w[ i ] ≤ 1000
人的權值 1 ≤ b[ i ] ≤ 1e6
解法:
先用並查集將朋友圈都找出來。
dp[ i ][ j ] : 已考慮前 i 個朋友圈,剩下的重量為 j,此時可能的最大總權值。
時間 / 空間複雜度:
O( N * W )
int N, M, W; vi F; vi B; vi X, Y; void init(){ cin >> N >> M >> W; F = B = vi( N ); for( int i = 0; i < N; ++i ) cin >> F[ i ]; for( int i = 0; i < N; ++i ) cin >> B[ i ]; X = Y = vi( M ); for( int i = 0; i < M; ++i ) cin >> X[ i ] >> Y[ i ], --X[ i ], --Y[ i ]; } struct dsu{ vi fa; dsu( int sz ){ fa = vi( sz ); for( int i = 0; i < sz; ++i ) fa[ i ] = i; } int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); } int unite( int x, int y ){ int a = find( x ); int b = find( y ); if( a == b ) return 0; fa[ b ] = a; return 1; } }; dsu *uf; vvi dp; vvi group; void preprocess(){ uf = new dsu( N ); for( int i = 0; i < M; ++i ) uf->unite( X[ i ], Y[ i ] ); group = vvi( N ); for( int i = 0; i < N; ++i ) group[ uf->find( i ) ].emplace_back( i ); dp = vvi( N + 1, vi( W + 1, -INF ) ); dp[ 0 ][ W ] = 0; for( int i = 0; i < N; ++i ) for( int j = 0; j <= W; ++j ) if( dp[ i ][ j ] >= 0 ){ upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] ); int sb = 0, sf = 0; for( int k = 0; k < group[ i ].size(); ++k ){ if( j - F[ group[ i ][ k ] ] >= 0 ) upmax( dp[ i + 1 ][ j - F[ group[ i ][ k ] ] ], dp[ i ][ j ] + B[ group[ i ][ k ] ] ); sb += B[ group[ i ][ k ] ]; sf += F[ group[ i ][ k ] ]; } if( j - sf >= 0 ) upmax( dp[ i + 1 ][ j - sf ], dp[ i ][ j ] + sb ); } } void solve(){ cout << *max_element( dp[ N ].begin(), dp[ N ].end() ) << endl; }