HDU 5441——Travel——————【并查集+二分查界限】
Travel
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1313 Accepted Submission(s): 472
For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000. The Undirected Kingdom has n cities and mbidirectional roads, and there are q queries.
Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000. It takes Jack d minutes to travel from city a to city b and vice versa.
Then q lines follow. Each of them is a query consisting of an integer x where x is the time limit before Jack goes berserk.
Note that (a,b) and (b,a) are counted as different pairs and a and b must be different cities.
10000
13000
题目大意:无向图。给你m条边,u - v 每条边有一个权值w。表示从城市u - v、v - u 的时间是w。然后q次询问。每次询问一个x值。表示问你当时间容忍为x时,可以走多少个城市对。每次到一个城市后可以休息,时间容忍会重新变为x。
解题思路:首先按边权把边排序。用并查集统计加入第k条边时可以走的城市对个数,记录在pair_cnt数组中。同时需要维护每个集合中的点的个数。最后在排完序后的边中二分找到第一个大于x的边的编号ck。然后在pair_cnt数组中找到编号ck-1即为答案。
#include<bits/stdc++.h>
using namespace std;
const int maxn=(1e4)*3;
const int maxm=1e5+200;
const int INF=0x3f3f3f3f;
struct Edge{
int u,v,w;
Edge(){}
Edge(int _u,int _v,int _w){
u=_u; v=_v; w=_w;
}
}edges[maxm];
int cnt[maxn],pair_cnt[maxm];
int fa[maxn];
void init(int n){
for(int i=0;i<=n;i++){
fa[i]=i;
cnt[i]=1;
}
}
int Find(int x){
if(fa[x]!=x){
return fa[x]=Find(fa[x]);
}
return x;
}
int Union(int u,int v){
int fu=Find(u);
int fv=Find(v);
int ret;
if(fu<fv){
ret=cnt[fu]*cnt[fv]*2;
fa[fv]=fu;
cnt[fu]+=cnt[fv];
return ret;
}else if(fu>fv){
ret=cnt[fu]*cnt[fv]*2;
fa[fu]=fv;
cnt[fv]+=cnt[fu];
return ret;
}else{
return 0;
}
}
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int BinSearch(int l,int r,int key){
while(l<r){
int md=(l+r)/2;
if(key<edges[md].w){
r=md;
}else if(key>edges[md].w){
l=md+1;
}else{
return md+1;
}
}
return r;
}
int main(){
int t,n,m,q;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&q);
init(n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
}
sort(edges+1,edges+1+m,cmp);
edges[0].w=-1;edges[m+1].w=INF;
for(int i=1;i<=m;i++){
pair_cnt[i]=pair_cnt[i-1]+Union(edges[i].u,edges[i].v);
}
int tmp;
for(int i=0;i<q;i++){
scanf("%d",&tmp);
printf("%d\n",pair_cnt[BinSearch(0,m+1,tmp)-1]);
}
}
return 0;
}
最新文章
- Thinking in java学习笔记之interface
- 【BZOJ1671】[Usaco2005 Dec]Knights of Ni 骑士 BFS
- 【6集iCore3_ADP触摸屏驱动讲解视频】6-1 工程及程序构架介绍
- ajax 通用方法,从thinkphp中拔出来的
- Sql Server中不常用的表运算符之PIVOT
- Episode 388: Testing vs Monitoring
- SQL Server 插入数据后获得自增主键值
- (BFS)uva2554-Snakes &; Ladders
- Server Develop (五) Linux并发模型
- 设计模式系列 1——StaticFactory(静态工厂),AbstractFactory(抽象工厂)
- struts2使用struts2-bootstrap-plugin插件
- phpize php扩展模块安装
- MVC和Web API 过滤器Filter [转]
- MYSQL使用指南(下)
- Dataguard配置前提条件
- ThinkPHP - 独立分组项目搭建
- 动态传递参数到DevExpress.XtraReports的小结
- Java之戳中痛点 - (6)避免类型自动转换,例如两个整数相除得浮点数遇坑
- 10年java过来人聊聊自己的自学、培训和工作经历
- FPGA配置OV5640摄像头及RGB图像数据采集