正文

并查集的一般操作②

aidenpearce  aidenpearce  2022-10-09  614

关键词：

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有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

输出格式：

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

输入输出样例

输入：　　　　　　输出：

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

Solution

通过观察，发现是一道并查集和01背包的好水题；

只要把链接的云并成一组，然后对这些组进行dp就行了；

详见代码

#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,w;int val[100010],wt[100010];
///**并查集**///
struct b
{
    int par[100010];
    inline void  ih(){for(int i=1;i<=n;i++)par[i]=i;}
    int f(int x){return par[x]=(par[x]==x)?x:f(par[x]);}
    int u(int x,int y)
    {

        val[f(x)]+=val[f(y)];
        wt[f(x)]+=wt[f(y)];
        par[f(y)]=f(x);
    }
}s;
int a,b;
int ans,dp[100010];
int val1[100010];int wt1[100010];int main()
{
    //freopen("in","r",stdin);
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&wt[i],&val[i]);
    }
    s.ih();
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        s.u(a,b);
    }
    int sum=1;
    for(int i=1;i<=n;++i)　　　　　　　　/// 巧妙的操作
    {
        if(s.par[i]==i)
        {
            val1[sum]=val[s.f(i)];
            wt1[sum]=wt[s.f(i)];
            sum++;
        }
    }
///**01背包*////
    for(int i=1;i<=sum;++i)
    {
       for(int j=w;j>=wt1[i];--j)
        {
            dp[j]=max(dp[j],dp[j-wt1[i]]+val1[i]);
        }
    }
    printf("%d",dp[w]);
}

View Code

21:07:43

并查集的一般操作③

RT 题目描述 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同... 查看详情

并查集的一般操作①

Rt 题目背景A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修... 查看详情

数据结构--并查集的原理及实现(代码片段)

一，并查集的介绍并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。而在某次合并之后，有一种... 查看详情

并查集的基本操作和用法(代码片段)

并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情

并查集的基本操作和用法(代码片段)

并查集的删除操作(代码片段)

...一开始所有信件都是单独的文件夹。其实就是一个简单的并查集删除的操作，当删除时就创建新的结点来代替它,要注意的是数组的范围，虽然信件只有10的5次方，但是操作有10的6次方，因为删除时还得查看详情

❤️数据结构入门❤️（2-5）-并查集

文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情

hdu2473junk-mailfilter(并查集的删除操作)

ProblemDescriptionRecognizingjunkmailsisatoughtask.Themethodusedhereconsistsoftwosteps:1)Extractthecommoncharacteristicsfromtheincomingemail.2)Useafiltermatchingthesetofcommoncharacteristicsextractedt 查看详情

并查集的简介

　　最近做题用到了并查集索性就把自己所掌握的相关知识总结一下。　　并查集(union-findsets),CLRS上称为disjoint-set,是一组不相交的动态集合S1,S2,....Sk。它能够实现较快的合并和判断元素所在集合的操作，应用比较广泛，如其求... 查看详情

hdu2473junk-mailfilter(并查集的删除操作)

...来。。如今又做了做，还是没做出来。。、、这题涉及到并查集的删除操作。想到了设一个虚节点，可是我把虚节点设为了要删除的点的父节点。一直是栈溢出，目測是无限递归了。看了看别人的做法。原来仅仅要建一个映射就... 查看详情

并查集

并查集1.并查集是什么并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。查询元素a和元素b是否属于同一组。合并元素a和元... 查看详情

数据结构——并查集的详细解析和实现(代码片段)

...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查查看详情

数据结构——并查集的详细解析和实现(代码片段)

朋友(并查集的删除操作可看作是插入操作的逆序)

小z被选为他们村的村长，现在小z调查他们村上的关系。如果村民a和村民b是朋友，村民b和村民c是朋友，那么村民a和村民c也是朋友。那么村上的村民就会形成一个“朋友”团队，现在小z想知道他们村长有多少个这样的团队。同... 查看详情

restructuringcompany和almostunion-find并查集的区间合并与并查集的删除

RestructuringCompany Eventhemostsuccessfulcompanycangothroughacrisisperiodwhenyouhavetomakeaharddecision—torestructure,discardandmergedepartments,fireemployeesanddootherunpleasantstuff.Let‘sconsi 查看详情

数据结构-树并查集的定义及其操作(代码片段)

...化3查找操作4并操作1数据结构定义#defineMAX50intUFSets[MAX];//并查集2初始化//参数：并查集SvoidInit(intS[])inti;for(i=0;i<MAX;i++)S[i]=-1;【注】根结点可用来保存该子集合的元素个数（负数表示）。3查找操作寻找包... 查看详情

并查集的优化及应用

2018-05-0115:13:08并查集是一个时空复杂度非常优越的数据结构，并且通过优化后其复杂度为<O(1)，O(n)>。并查集的优化主要有两个方面：路径压缩按rank来合并路径压缩：按rank合并：publicclassUnionFindSetprivateint[]parent;privateint[]rank;p... 查看详情

关于并查集的一切全在这里了(代码片段)

文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情