Codeforces Round #383 (Div. 2) D. Arpa's weak amphitheater and Mehrdad's valuable Hoses 并查集+双重01背包

My Soluton

题意：一堆人，这些人构成一些集合，2个元素至少有一条路径则为同一个集合，对于这些集合每个交合要么全取要不去不超过一个人，且每个人有一个wi和ai，要求在总wi小于等于w的情况下，是总ai最大

并查集+双重01背包

先用并查集处理出ptr-1个集合，然后对于这ptr-1个集合要么全取要么去不大于1个，跑一边01背包。

dp[i][j]表示到第i个背包是，总消耗容量j是最多装 dpij的东西。

复杂度 O(N^2)

#include 
#include 
#include 
#include 



#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int maxn = 1e3 + 8;

int father[maxn], _rank[maxn];

inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
    }
}

inline int _find(int v)
{
    return father[v] = father[v] == v ? v : _find(father[v]);
}

inline int _merge(int x, int y)
{
    int a = _find(x), b = _find(y);
    if(_rank[a] < _rank[b]){
        father[a] = b;
    }
    else{
        father[b] = a;
        if(_rank[a] == _rank[b]){
            _rank[a]++;
        }
    }
}

int w[maxn], a[maxn], sz[maxn], sum[maxn];
map<int, vector > mp;
map<int, int> Ind;
int dp[maxn][maxn];

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 2;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, sumw, findi;
    cin >> n >> m >> sumw;
    DisjointSet(n);
    for(int i = 1; i <= n; i++){ cin >> w[i];
    }
    for(int i = 1; i <= n; i++){ cin >> a[i];
    }

    int u, v;
    while(m--){
        cin >> u >> v;
        if(_find(u) != _find(v)) _merge(u, v);
    }

    for(int i = 1; i <= n; i++){
        findi = _find(i);
        sz[findi] += w[i];
        sum[findi] += a[i];
        mp[findi].push_back(ii(w[i], a[i]));
    }

    //new a[maxn] and w[maxn]
    int ptr = 1;
    for(int i = 1; i <= n; i++){ if(sz[i] > 0){
            w[ptr] = sz[i];
            a[ptr] = sum[i];
            Ind[ptr] = i;
            //cout << sz[i] << " " << sum[i] << endl;
            ptr++;
        }
    }

    int i, j;
    for(i = 1; i < ptr; i++){
        for(j = 0; j <= sumw; j++){ dp[i][j] = dp[i-1][j]; if(j != 0){ dp[i][j] = max(dp[i][j], dp[i][j-1]); } if(j - w[i] >= 0){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + a[i]);
            }
            //else dp[j][0] = max(dp[i][j][0], max(dp[i-1][j][0], dp[i-1][j][1]));
            for(auto k = mp[Ind[i]].begin(); k != mp[Ind[i]].end(); k++){
                if(j - (k->first) >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-(k->first)] + (k->second));
            }
        }
    }

    cout << dp[ptr-1][sumw] << endl;


    #ifdef LOCAL
    memset(_rank, 0, sizeof _rank);
    memset(sz, 0, sizeof sz);
    memset(sum, 0, sizeof sum);
    memset(dp, 0, sizeof dp);
    mp.clear();
    Ind.clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #383 (Div. 2) D. Arpa’s weak amphitheater and Mehrdad’s valuable Hoses 并查集+双重01背包

相关推荐

UVa 12186 Another Crisis dp：树上dp

2016 UESTC Training for Dynamic Programming H – 柱爷大战滑稽王 LCS转LIS

Good Bye 2016 D. New Year and Fireworks dp+枚举、状态总数

HDU 5904 LCIS __ dp、LCIS

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类