蒟蒻0pts求调!(悬关,先到先得)
查看原帖
蒟蒻0pts求调!(悬关,先到先得)
1004336
Hope5365楼主2023/11/30 21:24

马蜂丑,请各位dalao们多多见谅

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int n,m,w,c[N],d[N],f[N],dp[N];

int find(int x)
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> n >> m >> w;
    for(int i = 1;i <= n;i ++)
        scanf("%d%d",&c[i],&d[i]),f[i] = i;
    for(int i = 1;i <= m;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int fx = find(x),fy = find(y);
        f[fx] = fy,c[fx] += c[fy],d[fx] += d[fy];
    }
    for(int i = 1;i <= n;i ++)
        if (f[i] == i)
            for(int j = w;j >= d[i];j --)
                dp[j] = max(dp[j],dp[j - d[i]] + c[i]);
    cout << dp[w] << endl;
    return 0;
}
2023/11/30 21:24
加载中...