本文共 2074 字，大约阅读时间需要 6 分钟。
#include#include #include #include using namespace std;const int n_max = 2e4 + 5;const int m_max = 1e5 + 5;struct node{ int op; int ed; int len; bool operator < (const node Next) const { return len < Next.len; }} edge[m_max];struct query{ int id; int value; bool operator < (const query Next) const { return value < Next.value; }} Q[5005];int root[n_max];int sum[n_max];int T, n, m, q;int a, b, d;int ans[5005];int Find(int x){ return root[x] == x ? x : root[x] = Find(root[x]);}inline void Merge(int x, int y) // 指定根节点-----根节点的sum[]最大 累积 每个根 已连接的 点 的个数{ x = Find(x); y = Find(y); if (sum[x] > sum[y]) { sum[x] += sum[y]; root[y] = x; } else { sum[y] += sum[x]; root[x] = y; }}int main(){ scanf("%d", & T); while(T --) { scanf("%d %d %d", & n, & m, & q); for(int i = 0; i < m; i ++) scanf("%d %d %d", & edge[i].op, & edge[i].ed, & edge[i].len); sort(edge, edge + m); for(int k = 0; k < q; k ++) { scanf("%d", & Q[k].value); Q[k].id = k; } sort(Q, Q + q)； for(int i = 1; i <= n; i ++) { root[i] = i; sum[i] = 1; } int res=0; int i, j; i = j = 0; for ( ;i < q; i ++) { for ( ; j < m && edge[j].len <= Q[i].value; j ++) { if (Find(edge[j].op) == Find(edge[j].ed)) continue; res += sum[Find(edge[j].op)] * sum[Find(edge[j].ed)]; //配对 相当于两个根连接， 每个根分别包含 sum个 点，共有多少种两两组合 Merge(edge[j].op, edge[j].ed); } ans[Q[i].id] = res; } for (i = 0; i < q; i ++) printf("%d\n", ans[i] << 1); } return 0;}
：
有个很暴躁的人，想坐车旅行n个城市。连接城市共有m条路（双向）。他坐在车上很不爽，每次最多忍耐x分钟。但是每站下车他又可以休息（重新计时）。总共有q次询问。问途中有多少条路他可以不爆发。
a到b 和 b到a 算不同的路。 a 和 b 必须不相同。题解：
TLE无数，一开始先SPFA，再是用并查集，但是依旧超时。后来就用这种…将所有的询问按从小到大排列，之后每一次并查集都是在上一次查询的基础上进行，可以大大减少时间。
转载地址：http://hctpi.baihongyu.com/