博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 5441 (并查集)
阅读量:5856 次
发布时间:2019-06-19

本文共 751 字,大约阅读时间需要 2 分钟。

题意:给你n个点,m条边构成无向图。q个询问,每次一个值,求有多少条路,路中的边权都小于这个值

a->b 和 b->a算两种

思路:把权值从小到大排序,询问从小到大排序,如果相连则用并查集相连形成联通块

x个点可以形成:x * (x - 1)

如果新增的路使两个联通块和并则数量 增长了:

(num[1]+num[2])×(num[1]+num[2]-1) - num[1] × (num[1]-1) - num[2] ×(num[2]-1)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;int T,n,m,k;int num[20005],par[20005],p[20005];struct node{ int u,v,w; bool operator<(const node&a)const { return w < a.w; }} pnode[100005];struct term{ int id,we; bool operator<(const term&a)const { return we

  

转载于:https://www.cnblogs.com/Przz/p/5409758.html

你可能感兴趣的文章
ZOJ 3316 Game 一般图最大匹配带花树
查看>>
《系统架构师》——操作系统和硬件基础
查看>>
如何看待一本图书
查看>>
angularjs1-7,供应商
查看>>
oracle参数列表
查看>>
Wordpress3.2去除url中的category(不用插件实现)
查看>>
The 'Microsoft.Jet.OLEDB.4.0' provider is not registered on the local machine-Excel2003
查看>>
《Java 2 图形设计卷Ⅱ- SWING》第12章 轻量容器
查看>>
macOS Sierra 代码显示未来 Mac 将搭载 ARM 芯片
查看>>
《Arduino家居安全系统构建实战》——1.3 部署安全系统的先决条件
查看>>
Linux 中如何通过命令行访问 Dropbox
查看>>
《jQuery移动开发》—— 1.3 小结
查看>>
使用 Flutter 反序列化 JSON 的一些选项
查看>>
开发进度——4
查看>>
代码优化
查看>>
使用原理视角看 Git
查看>>
Node.js 的module 系统
查看>>
经典c程序100 例
查看>>
Fast enumerate
查看>>
页面中富文本的使用
查看>>