最小生成树，kruskal，并查集
题目意思：
n个点，m条边的图，双向边。问，权值是 len 的时候，有多少对点 x 和 y，可以从x 走到 y;
当权值 大于等于某条边的长度的时候，才能走那条边。 从点x 走到 y， 和从y 走到 x， 算是一个 点对。

本题要点：
1、实际模拟了 kruskal算法的过程。 每次选择一条当前最短的边（假设两点x, y, 边长 z），加入最小生成树，当点的两点 x 和 y
不属于同一个并查集的时候，这条边才被加入。 并且，如果 权值len == z 的时候，增加的可以走的点对的数量是
num[fay] * num[fax], fay， fax 分别是 点y和点x 所在并查集的父节点。
2、 用一个数组 merge_edge 来存放加入最小生成树的所有边。 数组merge_edge_num 则放对应的那条边可以走的点的对数。
3、 本题的查询量很大，需要处理好数组 merge_edge 和 merge_edge_num， 然后调用 stl 的 upper_bound 函数，
在 数组 merge_edge 查找第一个大于 当前查询的权值len的下标id, id - 1 表示 最后一个小于权值len的下标。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 10010, MaxM = 100010;
int fa[MaxN], num[MaxN];
int n, m, query;
int merge_edge[MaxN], cnt;	// merge_edge[k] 表示加入最小生成树的第k条边
int merge_edge_num[MaxN];	//merge_edge_num[k] 表示边长不超过最小生成树的第k条边，可以走的点的对数struct rec
{int x, y, z;bool operator<(const rec& rhs) const{return z < rhs.z;}
}edge[MaxM];int get(int x)
{if(x == fa[x])return x;return fa[x] = get(fa[x]);
}void solve()
{cnt = 0;sort(edge + 1, edge + m + 1);	for(int i = 1; i <= n; ++i){fa[i] = i, num[i] = 1;}int sum = 0;for(int i = 1; i <= m; ++i){int x = get(edge[i].x), y = get(edge[i].y);if(x == y)	continue;fa[x] = y;sum += num[y] * num[x];num[y] += num[x];merge_edge[++cnt] = edge[i].z;merge_edge_num[cnt] = sum;		}int len;for(int i = 0; i < query; ++i){scanf("%d", &len);int id = upper_bound(merge_edge + 1, merge_edge + cnt + 1, len) - merge_edge;--id;printf("%d\n", merge_edge_num[id]);}
}int main()
{while(scanf("%d%d%d", &n, &m, &query) != EOF){for(int i = 1; i <= m; ++i){scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);	}solve();}return 0;
}/*
10 10 10
7 2 1
6 8 3
4 5 8
5 8 2
2 8 9
6 4 5
2 1 5
8 10 5
7 3 7
7 8 8
10
6
1
5
9
1
8
2
7
6
*//*
36
13
1
13
36
1
36
2
16
13
*/