# CFR 742 D. Arpa's weak amphitheater and Mehrdad's valuable Hoses ( DP, Knapsack, Union Find )

Problem - D - Codeforces

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;
}
```