hdu3938 Portal 离线的并查集

  离线算法是将全部输入都读入,计算出所有的答案以后再输出的方法。主要是为避免重复计算。类似于计算斐波那契数列的时候用打表的方法。

  题目:给一个无向图,求有多少个点对,使得两点间的路径上的花费小于L,这里路径上的花费是这样规定的,a、b两点之间所有的路径中的最大边的最小值。   
  当然题目上不是这么写的。它问的是有多少种路径,这里就比较模糊了,到底两个路径怎样才算是两种路径呢,这时候重新看题,可以发现,如果理解为路径中经过的点不同的话,题目中给的所谓两点间的花费这个定义就没有意义了,所以就可以猜测,题目要求的是有多少个点对了。
  明确题意后,再进行分析。对一个点对的所有路径,只要最短最大边的那条路径出现,其后的所有较大最大边的路径都是毫无意义的,那么不妨将所有的边按照权值从小对大进行排序,用并查集的方法,进行加边,已经连通的点就不再管。那么每次加边的时候,是将两个集合并在一起的过程,假设集合大小分为a,b,显然路径的种类是a*b个,此时对于所有大于集合中最大边的L,都要加上这个种类数了。

  那么,算法就明确了,为离线算法,先输入所有的边和L,对所有的L进行排序,对所有的边进行排序,都为从小到大,然后对每个L,将比其小的边权的边都并在一起,计算种类数即可。

  上面的两段来源于:http://blog.csdn.net/sdj222555/article/details/7439187

  有点感慨,如果没有读懂题目,真的无法做题。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=10010,M=50010;
 7 struct node
 8 {
 9     int u,v,w;
10 }edge[M];
11 bool cmp(const node &a, const node &b)
12 {
13     return a.w<b.w;
14 }
15 int f[N],r[N];
16 int n,m,q,cnt;
17 void init()
18 {
19     for(int i=0;i<=n;i++)
20     {
21         f[i]=i;r[i]=1;
22     }
23 }
24 int Find(int x)
25 {
26     if(x==f[x])  return x;
27     return f[x]=Find(f[x]);
28 }
29 void Link(int x,int y)
30 {
31     int a=Find(x), b=Find(y);
32     cnt=0;
33     if(a!=b)
34     {
35         f[b]=a;
36         cnt=r[a]*r[b];
37         r[a]+=r[b];
38     }
39 }
40 int ans[N];
41 struct NODE
42 {
43     int id,re,num;
44 }que[N];
45 bool cmp1(const NODE &a,const NODE &b)
46 {
47     return a.num<b.num;
48 }
49 bool cmp2(const NODE &a,const NODE &b)
50 {
51     return a.id<b.id;
52 }
53 int main()
54 {
55     //freopen("test.txt","r",stdin);
56     int i,j,k;
57     while(scanf("%d%d%d",&n,&m,&q)!=EOF)
58     {
59         init();
60         for(i=0;i<m;i++)
61             scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
62         for(i=0;i<q;i++)
63         {
64             scanf("%d",&que[i].num);
65             que[i].id=i;
66             que[i].re=0;
67         }
68         sort(edge,edge+m,cmp);
69         sort(que,que+q,cmp1);
70         k=0;
71         for(i=0;i<q;i++)
72         {
73             while(edge[k].w<=que[i].num&&k<m)
74             {
75                 int a=Find(edge[k].u), b=Find(edge[k].v);
76                 if(a==b) {k++; continue;}
77                 else
78                 {
79                     Link(edge[k].u,edge[k].v);
80                     que[i].re+=cnt;
81                     k++;
82                 }
83             }
84             if(i>0) que[i].re+=que[i-1].re;
85         }
86         sort(que,que+q,cmp2);
87         for(i=0;i<q;i++)
88             printf("%d
",que[i].re);
89     }
90     return 0;
91 }
View Code
原文地址:https://www.cnblogs.com/Potato-lover/p/3930375.html