题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 10010;

int p[N];
int cost[N], w[N];
int f[N];
int n, m, k;

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}
int main()
{
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i ++) p[i] = i;

    for (int i = 1; i <= n; i ++)
    {
        int a, b;
        cin >> a >> b;
        cost[i] = a, w[i] = b;
    }
    for (int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            w[b] += w[a];
            cost[b] += cost[a];
        }
    }
    int res = 0;

    for (int i = 1; i <= n; i ++)
        if (p[i] == i)
        {
            for (int j = k; j >= cost[i]; j --)
                f[j] = max(f[j - cost[i]] + w[i], f[j]);
        }
    cout << f[k] << endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla