题意:
根据输入的三个整数 n,m,q, 表示有 n 座城市, m 条路, q 次询问. 下面给出 m 行, 每行三个数 start,end,w, 分别是这条道路的起点城市, 终点城市,"权值". 然后给出 q 次询问的数值, 每次询问的结果是符合条件的路有多少条. 条件就是: 如果这条路的权值比给的限制值要小, 那么这条路就是可行的. 注意就是: 对于一条路的添加来说, 只要 a 到 b 之间有路, 那么符合条件的路就会有两条, 一条是 a 到 b, 还有一条是 b 到 a. 比如: 添加了两条路, a 到 b,b 到 c, 那么其实答案就是 6 条,(a,b),(a,c),(b,a),(b,c),(c,a),(c,b).
思路:
刚开始用常规的并查集做法来写, 发现会 TLE, 看了下数据, 我之前那种遍历方法绝对会超时啊...... 看到 q 次询问就不加思索的对每次询问进行遍历, 这样每次询问就要遍历一遍那 m 组数据, 虽然实际可能不用遍历完 m 组, 但是这个时间复杂度是很高的. 然后网上学习了下, 发现有一种方法很好, 那就是不光对 load[i].w 进行排序, 还可以对这 q 次询问的限制值进行排序这样的话只需要对 m 组数据遍历一次就够了. 貌似这种方法有个名称叫做 "离线处理"?(我个人理解应该是把查询的值先读入, 读入后不在线处理, 而是先存起来, 排序之后再在遍历 m 组数据的时候使用) 因为输出的时候是要按照输入时的顺序对应输出, 所以这里需要有个表示查询值编号的数据. 然后计算公式的话, 两个集合合并, 有增量有减量, 合并后原来那两个集合不存在了, 减量就是 n1*(n1-1),n2*(n2-1); 合并后新出现的新集合存在一个增量:(n1+n2)*(n1+n2-1).
代码:
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int maxn = 2e4 + 10;
- const int max_edge = 1e5 + 10;
- const int max_q = 5e3 + 10;
- int fa[maxn];
- int num[maxn]; // 记录这个集合中点的个数
- struct Load
- {
- int start;
- int end;
- int w;
- } load[max_edge];
- struct Qnode
- {
- int sum;
- int id; // 记录编号, 便于最后输出时是按编号输出
- } qnode[max_q];
- bool cmp1(Load a, Load b) // 按权值从小到大排序
- {
- return a.w <b.w;
- }
- bool cmp2(Qnode a, Qnode b) // 按限制值从小到大排序
- {
- return a.sum < b.sum;
- }
- void init(int n)
- {
- for(int i = 1; i <= n; i++)
- {
- fa[i] = i;
- num[i] = 1;
- }
- return;
- }
- int find(int x)
- {
- if(fa[x] == x)
- {
- return x;
- }
- else
- {
- return fa[x] = find(fa[x]);
- }
- }
- int main()
- {
- ios::sync_with_stdio(false);
- int t;
- int n, m, q;
- long long ans[max_q];
- cin>> t;
- while(t--)
- {
- cin>> n>> m>> q;
- init(n);
- for(int i = 1; i <= m; i++)
- {
- cin>> load[i].start>> load[i].end>> load[i].w;
- // 发现这个交换是多余的......
- /*if(load[i].start> load[i].end)
- {
- swap(load[i].start, load[i].end);
- }*/
- }
- sort(load + 1, load + 1 + m, cmp1);
- for(int i = 1; i <= q; i++)
- {
- cin>> qnode[i].sum;
- qnode[i].id = i; // 编号按顺序赋值
- }
- sort(qnode + 1, qnode + 1 + q, cmp2);
- int cnt = 1;
- long long tmp = 0;
- for(int i = 1; i <= m; i++) // 这里是直接遍历路径数据, 效率比我之前想的高多了......
- {
- int x = find(load[i].start);
- int y = find(load[i].end);
- while(load[i].w> qnode[cnt].sum && cnt <= q)
- {
- ans[qnode[cnt].id] = tmp; // 没有新的路添加, 所以答案还是 tmp, 暂时不变
- cnt++; // 当前这个小的 qnode 不能满足大于这条路的权值, 那么就继续往下看比当前大的 qnode 是否符合条件
- }
- if(x != y)
- {
- long long n1 = num[x], n2 = num[y];
- tmp += (n1 + n2) * (n1 + n2 - 1);
- tmp -= (n1 * (n1 - 1) + n2 * (n2 - 1));
- fa[x] = y;
- num[y] += num[x]; //x 合并到 y 上, 则 x 上点的个数也要加到 y 上
- }
- }
- while(cnt <= q) // 这里的意思是, 路径数据已经全部遍历完了, 可能询问还没有结束, 较小的询问已经处理过全部数据, 那么较大的也一定能
- {
- ans[qnode[cnt++].id] = tmp;
- }
- for(int i = 1; i <= q; i++)
- {
- cout << ans[i] << endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2713396.html