【luogu4185】 [USACO18JAN]MooTube [并查集]

小鱼儿 2021-11-16 05:44 242阅读 0赞

[P4185 \[USACO18JAN\]MooTube][P4185 _USACO18JAN_MooTube]

并查集好合并不好拆开 可以考虑离线 先读入 从大到小排序 再依次合并

技巧：不好断开就倒着来合并 JSOI2008 P1197 也是该思想

#include<bits/stdc++.h>
    using namespace std;
    #define Max(x,y) (x)<(y)?(y):(x)
    #define Min(x,y) (x)<(y)?(x):(y)
    #define ll long long
    #define rg register
    const int N=300000+5,M=1000000+5,inf=0x3f3f3f3f,P=9999973;
    int n,m,f[N],sz[N];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    int find(int x) {
        return f[x]==x?x:f[x]=find(f[x]);}
    void merge(int x,int y){
        int fx=find(x),fy=find(y);
        if(fx==fy) return;
        sz[fx]+=sz[fy],f[fy]=fx;
    }
    
    struct edge{
        int u,v,w;}e[N<<1];
    struct node{
        int k,v,pos,ans;}ask[N];
    bool cmp1(edge a,edge b){
        return a.w>b.w;}
    bool cmp2(node a,node b){
        return a.k>b.k;}
    bool cmp3(node a,node b){
        return a.pos<b.pos;}
    
    int main(){
    //    freopen("in.txt","r",stdin);
        rd(n),rd(m),f[n]=n,sz[n]=1;
        for(int i=1;i<n;++i) rd(e[i].u),rd(e[i].v),rd(e[i].w),f[i]=i,sz[i]=1;
        for(int i=1;i<=m;++i) rd(ask[i].k),rd(ask[i].v),ask[i].pos=i;
        sort(e+1,e+n,cmp1);
        sort(ask+1,ask+m+1,cmp2);
        for(int i=1,nxte=1;i<=m;++i){
            while(nxte<n&&e[nxte].w>=ask[i].k)
            merge(e[nxte].u,e[nxte].v),++nxte;
            ask[i].ans=sz[find(ask[i].v)]-1;
        }
    //    for(int i=1;i<=n;++i) printf("%d ",sz[i]);
        sort(ask+1,ask+m+1,cmp3);
        for(int i=1;i<=m;++i) printf("%d\n",ask[i].ans);
        return 0;
    }

转载于:https://www.cnblogs.com/lxyyyy/p/11220678.html

[P4185 _USACO18JAN_MooTube]: https://www.luogu.org/problemnew/show/P4185

发表评论取消回复

表情：

评论列表（有 0 条评论，242人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集 Ⅱ

\[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T

古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 279 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 314 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 301 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 308 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 367 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 370 阅读

相关【luogu4185】 [USACO18JAN]MooTube [并查集]

[P4185 \[USACO18JAN\]MooTube][P4185 _USACO18JAN_MooTube] 并查集好合并不好拆开可以考虑离线先读入从大到小排序再

小鱼儿/ 2021年11月16日 05:44/ 0 赞/ 243 阅读

相关并查集

例题： ![输入样例][20190805122001677.png] 输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判

Dear 丶/ 2021年11月11日 08:04/ 0 赞/ 388 阅读

相关并查集

一、算法解释用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S

桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 475 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 573 阅读