题解 P1455 【搭配购买】

AmadeusSG · 2018-12-02 19:22:29 · 题解

追求代码的整洁与完美~

本题先用并查集思想把配套的物品的价值和重量连起来，有点类似于图论中的缩点。

然后我们就可以看到这题就成了一道模板01，再一看数据，必须降维优化，用一遍滚动数组优化就能轻松AC啦！

下面是标准完美Ak代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,w;
int father[1000005],val[1000005],rmb[1000005];
int dp[10000005];
int getfather(int u)//寻父之路
{
    if(father[u]==u)return u; 
    father[u]=getfather(father[u]);
    return father[u];
}
void unio(int x,int y)//并查集
{
    int fx=getfather(x);//爸爸去哪儿
    int fy=getfather(y);
    if(fx!=fy)
    {
        father[fx]=fy;
        rmb[fy]+=rmb[fx];//累加起来
        val[fy]+=val[fx];
    }
}
int main()
{
    int i,j;
    cin>>n>>m>>w;
    for(i=1;i<=n;i++)
    {
        father[i]=i;
        cin>>rmb[i]>>val[i];
    }
    for(i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        unio(x,y);
    }
    for(i=1;i<=n;i++)//zeroone背包
    if(father[i]==i)//判断是否为根节点（主件）
    for(j=w;j>=rmb[i];j--)dp[j]=max(dp[j],dp[j-rmb[i]]+val[i]);
    cout<<dp[w];//完美结束
    return 0;
}