0w1

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

Problem - D - Codeforces

題意:
給每個人的重量和權值。再給每對朋友的關係。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;
}