luogu P1455 搭配购买

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云朵已经被老板编号为1，2，3，……,n,并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入输出格式

输入格式：

第1行n,m,w,表示n朵云，m个搭配和你现有的钱的数目

第2行至n+1行，每行ci,di表示i朵云的价钱和价值

第n+2至n+1+m ，每行ui,vi表示买ui就必须买vi,同理，如果买vi就必须买ui

输出格式：

一行，表示可以获得的最大价值

输入输出样例

输入样例#1： 

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出样例#1： 

1

思路：看完体面后，第一反应，这不明显的就是，把有搭配的物品全部的价格，价值共加为一个物品，然后将这些物品给做背包不就完事了；

#include<bits/stdc++.h>
using namespace std;
int n,m,money,fa[10001],w[10001],v[10001],f[10001],MAX;
int find(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&money);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        scanf("%d%d",&w[i],&v[i]);
    }
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int g=find(x),h=find(y);
        if(g!=h)
        {
            fa[g]=h;
            w[g]+=w[h];w[h]+=w[g];
            v[g]+=v[h];v[h]+=v[g];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            for(int j=money;j>=w[i];j--)
            {
                f[j]=max(f[j],f[j-w[i]]+v[i]);
                MAX=max(MAX,f[j]);
            }
        }
    }
    printf("%d",MAX);
}

　　啊哦！貌似加完的忘记清零了，尴尬。

#include<bits/stdc++.h>
using namespace std;
int n,m,money,fa[10001],w[10001],v[10001],f[10001],MAX;
int find(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&money);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        scanf("%d%d",&w[i],&v[i]);
    }
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int g=find(x),h=find(y);
        if(g!=h)
        {
            fa[g]=h;
//            w[g]+=w[h];v[g]+=v[h];
            w[h]+=w[g];v[h]+=v[g];
//            w[h]=0;v[h]=0;
            v[g]=0;w[g]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            for(int j=money;j>=w[i];j--)
            {
                f[j]=max(f[j],f[j-w[i]]+v[i]);
                MAX=max(MAX,f[j]);
            }
        }
    }
    printf("%d",MAX);
}