2.2日总结

第一题：搭配购买

题解：一看就是很普通的01背包问题，但是和查并集一起考了，首先我们需要把每个有联系的链接起来，形成一个大背包，用来装他们的总金额和总价值，然后我们在看一个个的物品进行取或者不取两种操作，但是这题需要进行状态压缩，不能用二维的dp数组，否则会MLE，要用一维的滚动数组来解决问题

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


int n,m,we;
int c[10005];
int d[10005];
int s[10005];
int w[10005];
int v[10005];
int w1[10005];
int v1[10005];
int dp[10005];
int cha(int x)
{
    if(s[x]==x)
        return x;
        s[x]=cha(s[x]);
    return s[x];
}
void bing(int root1,int root2)
{
    if(root1==root2)
    {
        return ;
    }
    else
    {
        if(root1>root2)
            s[root1]=root2;
        else
            s[root2]=root1;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&we);
    for(int i=1;i<=n;i++)
    {
        s[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&d[i]);
    }
    for(int i=0;i<m;i++)
    {
        int p,q;
        scanf("%d%d",&p,&q);
        bing(cha(p),cha(q));
    }
    for(int i=1;i<=n;i++)
    {
        w[cha(i)]+=c[i];
        v[cha(i)]+=d[i];
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(w[i]!=0&&v[i]!=0)
        {
            w1[k]=w[i];
            v1[k]=v[i];
            k++;
        }
    }
    for(int i=0;i<k;i++)
    {
        for(int j=we;j>=w1[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w1[i]]+v1[i]);
        }
    }
    printf("%d",dp[we]);
    return 0;
}

 第二题：刻录光盘

题解：相比于树，这题其实说是图实则更加贴切，因为这题有个考点就是A可以给B，但B不一定会给A,，因此我们用floyd算法去处理 才是最优解

#include<bits/stdc++.h>
using namespace std;
int n;
int f[300][300];
int s[300];
int b[300];
int cha(int x)
{
    while(s[x]!=x)
    {
        x=s[x];
    }
    return x;
}
void bing(int root1,int root2)
{
    while(root1!=s[root1])
        root1=s[root1];
    s[root2]=root1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        s[i]=i;
    }
    int z;
    for(int i=1; i<=n; i++)
    {
        while(1)
        {
            scanf("%d",&z);
            if(z==0)
                break;
            f[i][z]=true;
        }
    }

    //弗洛伊德算法
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(f[i][j])
            {
                bing(i,j);
            }
        }
    }
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        b[cha(i)]=1;
    }
    for(int i=1; i<=n; i++)
    {
        if(b[i]!=0)
            sum++;
    }
    printf("%d\n",sum);
    return 0;
}