链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3938
题意：给出 n个点，m条边的无向图，给出q次查询，每次的查询给出一个l，使得在l的范围下，建尽可能多的边，求问在建这些边的情况下，有多少条路径（任意两点可到达的对数）
题解：离线的并查集，刚开始的时候，暴力模拟，在每个并查集里边计算路径数目，果断T。。。正解：离线并查集，将每个查询保存起来，根据l排序，依次计算在每个l下可以有多少条路径，累加到每一个l。
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <queue> #include <map> #include <stack> #include <iostream> #define pi acos(-1.0) #define INF 0x3f3f3f3f using namespace std; #define ll long long const int maxn=50010; int n,m,q; int f[maxn],num[maxn]; struct edge { int u,v,w; bool operator < (const edge tmp) const { return w<tmp.w; } }e[maxn]; struct node { int id,l; bool operator < (const node tmp) const { return l<tmp.l; } }nd[maxn]; int found(int x) { if(x!=f[x]) f[x]=found(f[x]); return f[x]; } int Merge(int a,int b) { int fx=found(a),fy=found(b); if(fx==fy) return 0; //在集合中，已经计算过了 f[fx]=fy; int ans=num[fx]*num[fy]; num[fy]+=num[fx]; num[fx]=0; return ans; } int main() { //freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); //ios::sync_with_stdio(false); //freopen("C:\Users\Administrator\Desktop\b.txt","w",stdout); int ans[maxn]; while(scanf("%d%d%d",&n,&m,&q)!=EOF) { memset(ans,0,sizeof ans); for(int i=0;i<m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); for(int i=0;i<q;i++) { scanf("%d",&nd[i].l); nd[i].id=i; } sort(e,e+m); sort(nd,nd+q); for(int i=0;i<=n;i++) num[i]=1,f[i]=i; int pos=0,tmp=0; for(int i=0;i<q;i++) { while(pos<m&&nd[i].l>=e[pos].w) { tmp+=Merge(e[pos].u,e[pos].v); pos++; } ans[nd[i].id]=tmp; } for(int i=0;i<q;i++) printf("%d ",ans[i]); } return 0; }