首页 > 代码库 > (离线处理+并查集) hdu 3938
(离线处理+并查集) hdu 3938
Portal
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 977 Accepted Submission(s): 490
Problem Description
ZLGG found a magic theory that the bigger banana the bigger banana peel .This important theory can help him make a portal in our universal. Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge in the path. There may be lots of paths between two points. Now ZLGG owned L energies and he want to know how many kind of path he could make.
Input
There are multiple test cases. The first line of input contains three integer N, M and Q (1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,000). N is the number of points, M is the number of edges and Q is the number of queries. Each of the next M lines contains three integers a, b, and c (1 ≤ a, b ≤ N, 0 ≤ c ≤ 10^8) describing an edge connecting the point a and b with cost c. Each of the following Q lines contain a single integer L (0 ≤ L ≤ 10^8).
Output
Output the answer to each query on a separate line.
Sample Input
10 10 107 2 16 8 34 5 85 8 22 8 96 4 52 1 58 10 57 3 77 8 810615918276
Sample Output
36131133613621613
这题挺不错的，学到了离线算法。题目要求两点之间最大边的最小值小于某值的个数。其实就是求点对。
集合划分
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<string>#include<algorithm>#include<cstdlib>using namespace std;int n,m,q,set[50010],num[50010],ans[50010];struct node{ int x,y,w;}e[50010];struct nod{ int x,id;}aa[50010];bool cmp(node a,node b){ return a.w<b.w;}bool cmp1(nod a,nod b){ return a.x<b.x;}int find(int x){ if(x!=set[x]) set[x]=find(set[x]); return set[x];}int Union(int a,int b){ int fx,fy; fx=find(a),fy=find(b); if(fx==fy) return 0; int t=num[fx]*num[fy]; num[fx]+=num[fy]; num[fy]=0; set[fy]=fx; return t;}int main(){ while(scanf("%d%d%d",&n,&m,&q)!=EOF) { memset(e,0,sizeof(e)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) set[i]=i,num[i]=1; for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); } sort(e+1,e+1+m,cmp); for(int i=1;i<=q;i++) { scanf("%d",&aa[i].x); aa[i].id=i; } sort(aa+1,aa+1+q,cmp1); int k=1,cnt=0; for(int i=1;i<=q;i++) { while(k<=m&&e[k].w<=aa[i].x) { cnt+=Union(e[k].x,e[k].y); k++; } ans[aa[i].id]=cnt; } for(int i=1;i<=q;i++) printf("%d\n",ans[i]); } return 0;}
(离线处理+并查集) hdu 3938
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。