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

相关文章

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

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i