The 15th Chinese Northeast Collegiate Programming Contest K.CITY 离线单调+并查集连通+优先队列

本文主要是介绍The 15th Chinese Northeast Collegiate Programming Contest K.CITY 离线单调+并查集连通+优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

题意

n个节点,m条边,每条边都有权重,Q次询问,每次询问附带一个正整数x代表,有规模为x的军队,能通过权重>=x的路。如果两个节点能互相到达,则算一个有效对,求针对军队规模为x,有几个有效对。

解析

  1. 很容易的发现每次询问附带的军队规模x具有单调性,x如果越大,答案越小,反之答案越大。那么可以离线存储询问,对询问的规模进行排序,从规模大开始计算,然后越来越小,答案递增。
  2. 对于一个确定大小为 s s s的连通块,其对答案贡献是固定的为 s ∗ ( s − 1 ) 2 \frac{s*(s-1)}{2} 2s(s1),对于某两个连通块,因为x变小了,使得两个连通块链接在一起,变得更大了,我们只需要减去原两个的贡献度,维护连通块的算法当然是——并查集!
  3. 那么问题来了,我们如何根据答案变小而找出影响了哪些边呢?很简单用优先队列存边即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll f[N];
ll sz[N];
pair<int,int> qs[N];
ll ans[N];
int find(int i){return f[i]==i? i: f[i]=find(f[i]);
}
ll merge(int a,int b){if(a>b)swap(a,b);int fa=find(a),fb=find(b);f[fa]=fb;sz[fb]+=sz[fa];return sz[fb];
}
struct edge{ll u,v,w;bool operator < (const edge a)const{return  w<a.w;}
};
ll get(ll x){return x*(x-1)/2;
}
int main(){int t;scanf("%d",&t);while(t--){int n,m,q;scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){f[i]=i;sz[i]=1;}priority_queue<edge,vector<edge>>pq;for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);pq.push({u,v,w});}for(int i=1;i<=q;i++){scanf("%d",&qs[i].first);qs[i].second=i;}sort(qs+1,qs+1+q,greater<pair<int,int>>());ll res=0;
//        cout<<qs[1].first<<" "<<pq.top().w<<endl;for(int i=1;i<=q;i++){int x=qs[i].first;while(!pq.empty() && pq.top().w>=x){auto t=pq.top();pq.pop();int u=t.u;int v=t.v;if(find(u)!=find(v)){res-=get(sz[find(u)])+get(sz[find(v)]);res+=get(merge(u,v));}}ans[qs[i].second]=res;}for(int i=1;i<=q;i++){cout<<ans[i]<<endl;}}
}

这篇关于The 15th Chinese Northeast Collegiate Programming Contest K.CITY 离线单调+并查集连通+优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/897923

相关文章

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin