codevs 1450 xth 的旅行
毕业了,Xth很高兴,因为他要和他的 rabbit 去双人旅行了。他们来到了水城威尼
斯。众所周知(⊙﹏⊙b汗),这里的水路交通很发达,所以 xth 和 rabbit 只好坐
船穿梭于各个景点之间。但是要知道,rabbit 是会晕船的,看到她难受,xth 是会
心疼的。
已知城市中有n个景点,这些景点之间有m条双向水路,在每条水路上航行时
rabbit 都会有一个“晕船值”。旅行时,xth 会带着 rabbit 尽量选择晕船值小的路线
旅行。但是 rabbit 也是有一定忍耐限度度的,如果晕船值超过了她的忍耐度,xth
会果断决定放弃这条路线。
现在 xth 想进行若干次询问,给定 rabbit 的忍耐度,问还有多少对城市(x,y)间会存
在可行的旅行路线(如果(x,z)和(z, y)可行,则(x,y)可行,也就是说连通性是可传
递的)。
第 1 行三个正整数n、m、q,分别表示景点数量、水路数量和询问次数。
第 2 行到第m + 1行每行三个正整数x、y、w,表示x号景点和y号景点之间有一条
“晕船值”为w的双向水路。
第m + 2行至第m + q + 1行,每行一个正整数k,表示询问中给定的 rabbi忍耐度
为k。
共q行,对于每次询问做出回答。
5 5 2
1 2 1
2 3 2
3 4 1
4 5 4
5 1 1
1
2
4
10
第一个询问:(1,2), (1,5), (2,5), (3,4)。其中(2,5)的具体走法为:2 − 1 − 5
第二个询问:(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)。其中(4,5)
的具体走法为:4 − 3 − 2 − 1 − 5
对于20%的数据满足n ≤ 20,m ≤ 40,q ≤ 40;
对于40%的数据满足n ≤ 1000,m ≤ 2000,q ≤ 1000;
对于60%的数据满足n ≤ 3000,m ≤ 6000,q ≤ 200000;
对于100%的数据满足n ≤ 100000,m ≤ 200000,q ≤ 200000。其他数不超过10
9。
并查集离线水题
#include<bits/stdc++.h>
#define ll long long
#define maxn 200005
using namespace std;
struct lines{
int u,v,w;
bool operator <(const lines &U)const{
return w<U.w;
}
}l[maxn];
struct node{
int a,num;
bool operator <(const node &U)const{
return a<U.a;
}
}q[maxn];
int n,m,Q;
int siz[maxn],p[maxn];
ll now=0,ans[maxn]; int ff(int x){
return p[x]==x?x:(p[x]=ff(p[x]));
} inline void update(lines x){
int fa=ff(x.u),fb=ff(x.v);
if(fa!=fb){
now+=siz[fa]*(ll)siz[fb];
p[fa]=fb;
siz[fb]+=siz[fa];
}
} inline void solve(){
sort(q+1,q+Q+1);
sort(l+1,l+m+1); int linenum=0;
for(int i=1;i<=Q;i++){
while(linenum<m&&l[linenum+1].w<=q[i].a){
update(l[linenum+1]);
linenum++;
}
ans[q[i].num]=now;
}
} int main(){
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++) siz[i]=1,p[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l[i].u,&l[i].v,&l[i].w);
}
for(int i=1;i<=Q;i++){
scanf("%d",&q[i].a);
q[i].num=i;
} solve(); for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
return 0;
}
最新文章
- delphi 事件和属性的绑定
- [转]MySQL Explain详解
- 搭建Maven工程的时候,做单元测试,报ClassNotFoundException
- [原]My first Python
- 树莓派做web服务器(nginx、Apache)
- VIM IDE
- WCF基金会
- JavaScript闭包小窥
- asp.net URL DES加密 什在URL中的使用
- [编织消息框架][rpc]使用篇
- iOS上机题(附个人见解)
- weakhashmap简单理解
- java中的多线程入门
- SQL Server 深入解析索引存储(堆)
- thymeleaf资源加载问题(从Controller跳转)
- shell编程 之 实践出真知(代码实例)
- Docker 常用命令(四)
- 2nd,Python基础2——02
- POJ-3693/HDU-2459 Maximum repetition substring 最多重复次数的子串(需要输出具体子串,按字典序)
- android 开发 实现RecyclerView的列表单选功能
热门文章
- loj6392 「THUPC2018」密码学第三次小作业 / Rsa
- 图说不为人知的IT传奇故事-1-计算机新生
- Docker danriti/nginx-gunicorn-flask 使用
- Composer 下载安装类库
- 【bzoj3028】食物 数论+生成函数
- HDU 4391 Paint The Wall(分块+延迟标记)
- [AHOI2014&;&;JSOI2014][bzoj3876] 支线剧情 [上下界费用流]
- ofbiz16 idea 启动
- Long.ValueOf(";String";) Long.parseLong(";String";) 区别 看JAVA包装类的封箱与拆箱
- Jury Compromise(poj 1015)