首页 > 代码库 > hdu 3948 Portal (kusral+离线)
hdu 3948 Portal (kusral+离线)
Portal
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 931 Accepted Submission(s): 466
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
Source
2011 Multi-University Training Contest 10 - Host by HRBEU
题目意思:
给定一张无向图，要你求出满足小于或等于给定边长的最多边长的种类数目。当然关键是有n次询问。
思路：
对于一颗有n条路径的无向图，可以知道，当与另一个m条路径的无向图合并为一个全新的无向图时： 此时的路径为 n*m;
当然这题的重点不在这里，此题关键是有q次询问，对于每一次询问，若我们都去重新求解一次，将会很花时间，无疑TLE倒哭。%>_<%
于是采用离线处理（这里是开了解题报告才想起来，这么巧妙的地方，果然是too yong 哇！ ）：
离线的思路为： 先将询问的权值从小到大排序，由于大的权值包含了小的权值，于是整个过程，居然只需要一次就搞定。 俺是乡下人，第一次见识到这点，吓尿了！╮(╯▽╰)╭
代码：
1 #define LOCAL 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<cstdlib> 7 using namespace std; 8 const int maxn=10005; 9 /*for point*/10 struct node{11 int a,b,c;12 bool operator <(const node &bn)const {13 return c<bn.c;14 }15 }sac[maxn*5];16 /*for query*/17 struct query{18 int id,val;19 bool operator <(const query &bn)const {20 return val<bn.val;21 }22 }qq[maxn];23 24 int father[maxn],rank[maxn];25 int key[maxn];26 27 void init(int n){28 for(int i=0;i<=n;i++){29 father[i]=i;30 rank[i]=1;31 }32 }33 34 int fin(int x){35 while(x!=father[x])36 x=father[x];37 return x;38 }39 40 int unin(int x,int y)41 {42 x=fin(x);43 y=fin(y);44 int ans=0;45 if(x!=y){46 ans=rank[x]*rank[y];47 if(rank[x]<rank[y]){48 rank[y]+=rank[x];49 father[x]=y;50 }51 else{52 rank[x]+=rank[y];53 father[y]=x;54 }55 }56 return ans;57 }58 59 int main()60 {61 #ifdef LOCAL62 freopen("test.in","r",stdin);63 freopen("test1.out","w",stdout);64 #endif65 int n,m,q;66 while(scanf("%d%d%d",&n,&m,&q)!=EOF)67 {68 init(n);69 for(int i=0;i<m;i++){70 scanf("%d%d%d",&sac[i].a,&sac[i].b,&sac[i].c);71 }72 73 for(int i=0;i<q;i++){74 scanf("%d",&qq[i].val);75 qq[i].id=i;76 }77 sort(sac,sac+m);78 sort(qq,qq+q);79 int i,j,res=0;80 for(j=0,i=0;i<q;i++){81 while(j<m&&sac[j].c<=qq[i].val){82 res+=unin(sac[j].a,sac[j].b);83 ++j;84 }85 key[qq[i].id]=res;86 }87 for(i=0;i<q;i++){88 printf("%d\n",key[i]);89 }90 }91 // system("comp");92 93 return 0;94 }
hdu 3948 Portal (kusral+离线)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。