Travel
Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u
/*
题意
给出n【节点数】,m【连线数】,q【查询次数】;
输入m组数据 u【起点】,v【终点】,cost【权值】; (u,v)和 (v,u)表示两种不同的连线
输入q组查询数据； 要求
输出在m组数据中所有cost<q的所有节点连线的连线方式个数。 注意：每个拥有n个节点的联通块有 n*(n-1)个联通分量 （连线数）；
每次两个联通块相连总连线数应该是(n1+n2)*(n1+n2-1)；
用一个数据来记录的话更新方式应该为 n-n1*(n1-1)-n2*(n2-1)+(n1+n2)*(n1+n2-1);
*/ //如果每一次都重新建立并查集，查询数q比较大的话肯定会超时的，看了别人博客说用离线思维；稍稍了解了一下啥叫离线思维。 //本题用离线思想，将查询按照X的大小升序排序，后面的查询就在前一步往后进行，复杂度减小很多
/*
神测试数据。。。。。【 T。T 】
1
5 5 12
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6333
6334
6335
12345
12381
12385
13000
233
5777
21726
21727
21725
*/
//AC代码：
#include"iostream"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"algorithm"
using namespace std;
const int MX=2222222;
long long ans[MX];
int P[MX], num[MX]; struct node {
int u, v, cost;
} side[MX]; bool cmp_side(node a,node b) {
return a.cost < b.cost;
} struct Que {
int id, x; //id 记录输入时候的顺序 x记录查询值
} Q[MX]; bool cmp_que(Que a,Que b) {
return a.x<b.x;
} int find(int x) {
return P[x]==x?x:(P[x]=find(P[x]));
} int main() {
int T;
scanf("%d", &T);
while(T--) {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i=1; i<=n; i++) {
P[i]=i;
num[i]=1; //初始化连通分量
}
for(int i=1; i<=m; i++) { //把无向边加入队列
scanf("%d%d%d", &side[i].u, &side[i].v, &side[i].cost);
}
sort(side+1,side+m+1,cmp_side);//升序排序无向边
for(int i=1; i<=q; i++) { //添加查询队列
Q[i].id=i;
scanf("%d",&Q[i].x);
}
sort(Q+1,Q+q+1,cmp_que); //按照查询复杂度排序答案。
int k=1;
long long s=0;
for(int i=1; i<=m; i++) {
while(k<=q&&side[i].cost>Q[k].x)ans[Q[k++].id]=s; //把答案按照ID的顺序保存到ans数组中
int rt1=find(side[i].u),rt2=find(side[i].v);
if(rt1!=rt2) {
long long n1=num[rt1],n2=num[rt2];
//每个拥有n个节点的联通块有 n*(n-1)个联通分量 （对点）
s=s-n1*(n1-1)-n2 *(n2-1)+(n1+n2)*(n1+n2-1);//去掉两个根的联通量在加上总和的联通分量
P[rt1]=rt2;
num[rt2]+=num[rt1];//加上节点的数量
}
}
//ans[Q[k].id]=s; // 【这里居然看在上面读入ans之后还没有到最后一个，后面再测试数据才发现了这个问题。。。】
while(k<=q)
ans[Q[k++].id]=s;
for(int i=1; i<=q; i++)
printf("%I64d\n",ans[i]); //按照离线保存的实际查询顺序输出
}
return 0;
}