Codeforces B.Arpa's weak amphitheater and Mehrdad's ...

Description

n人分属不同的朋友圈，这些人都有自己的体重w与美丽度b，他们之间有m个关系描述（是朋友）。有一个舞台最大承重w，从每个朋友圈中选一个人或全选，在不超重前提下选美丽度最大的情况。

http://codeforces.com/problemset/problem/741/B

思路

题目有个关于两个人属于同一朋友圈的叙述：

Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, …, ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

AB、BC属于同一个圈，则AC属于同一个圈

AB、BC、CD属于同一个圈，则AD属于同一个圈

仔细想想其实就是个并查集

选一个或‘全都要’：

将’全都要‘等效成新的‘一个’，即将‘特殊’一般化

接下来背包DP，不过我没看出来‘每组只取一个’体现在哪？重量循环在外层？可以问问师哥

Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int N, M, W, x, y;
int w[10005];
int b[10005];
int pre[10005];
int dp[1005];
vector<int> vec[10005];

void init()
{
    for(int i = 0; i <= N; ++i)
        pre[i] = i;
}

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

void unite(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
        pre[y] = x;
}

int main()
{
    cin >> N >> M >> W;
    ///1. 初始化与输入
    init();
    for(int i = 1; i <= N; ++i)
        scanf("%d", &w[i]);
    for(int i = 1; i <= N; ++i)
        scanf("%d", &b[i]);

    ///2. 并查集分组
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d", &x, &y);
        unite(x, y);
    }
    for(int i = 1; i <= N; ++i)
        vec[ found(i) ].push_back(i);

    ///3. 枪打出头鸟：特殊一般化
    ///"全拿"等效成"新的一组"
    int num = N + 1;
    for(int i = 1; i <= N; ++i)
    {
        if(vec[i].size() == 0)
            continue;

        int sz = vec[i].size();
        int ww = 0, bb = 0;
        for(int j = 0; j < sz; ++j)
        {
            ww += w[ vec[i][j] ];
            bb += b[ vec[i][j] ];
        }
        w[num] = ww;
        b[num] = bb;
        vec[i].push_back(num++);
    }

    for(int i = 1; i <= N; ++i)///某个非空集合num
    {
        if(vec[i].size() == 0)
            continue;

        ///哪里体现了"从每个集合里只选一个"的要求？
        int sz = vec[i].size();
        for(int j = W; j >= 1; --j)
            for(int k = 0; k < sz; ++k)///非空集合num中每个元素
                if(j >= w[ vec[i][k] ])/// >= 别漏了'='
                    dp[j] = max(dp[j], dp[j - w[ vec[i][k] ]] + b[ vec[i][k] ]);
        ///每个集合循环一次才决定了一个dp[j]，每个集合只对应一个dp[w]
        ///最终的dp[w]是最优的
    }
    cout << dp[W] << '\n';
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92