70分wa1,3,4
  • 板块P1455 搭配购买
  • 楼主Moddy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/31 10:31
  • 上次更新2024/5/31 15:46:43
查看原帖
70分wa1,3,4
863562
Moddy楼主2024/5/31 10:31

错在哪捏

#include<bits/stdc++.h>
using namespace std;

int par[10005];
int c[10005]; //价值
int f[10005]; //花费
int res[10005];
int find(int x)
{
    if(par[x]==x)
        return x;
    return par[x]=find(par[x]);
}

int main()
{
    int n,m,w;
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        cin>>f[i]>>c[i];
    }
    for(int i=1;i<=n;i++)
        par[i]=i;
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        //合并物品
        if(find(u)!=find(v))
        {
            par[v]=u;
            f[u]+=f[v];
            c[u]+=c[v];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        if(par[i]==i)
        {
            for(int j=w;j>=0;j--)
            {
                if(j>=f[i]){
                    res[j]=max(res[j],res[j-f[i]]+c[i]);
                }
            }
        }
    }
    cout<<res[w];
    return 0;
}
2024/5/31 10:31
加载中...