这题计算 一张图上 能走的 点对有多少个  对于每个限制边权 , 对每条边排序,对每个查询排序

然后边做克鲁斯卡尔算法 的时候变计算就好了

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn=;
typedef long long LL;
struct edg{
int a,b,d;
edg(int ca=,int cb=,int cd=)
{
a=ca; b=cb; d=cd;
}
bool operator <(const edg &rhs)const{
return d<rhs.d;
}
}E[];
struct query{
LL id,d;
query(LL cid=, LL cd= ){
id=cid; d=cd;
}
bool operator <(const query &rhs)const {
return d<rhs.d;
}
}Q[];
LL S[maxn];
LL num[maxn];
int fa[maxn];
int fin(int a)
{
return fa[a]=(fa[a]==a)?a:fin(fa[a]);
}
LL ans[];
int main()
{ int cas;
scanf("%d",&cas);
for(int cc=; cc<=cas; cc++)
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=; i<m; i++)scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].d);
for(int i=; i<=n; i++){fa[i]=i;S[i]=;num[i]=;}
for(int i=; i<q; i++) {scanf("%I64d",&Q[i].d);Q[i].id=i; ans[i]=;}
sort(E,E+m);
sort(Q,Q+q);
int loc=;
LL D=;
for(int i=; i<q; i++)
{
while(loc<m&&E[loc].d<=Q[i].d){
int a=E[loc].a,b=E[loc].b;
a=fin(a);
b=fin(b);
if(a==b){ loc++; continue; }
D=D-S[a]-S[b];
fa[b]=a;
num[a]+=num[b];
S[a]=1LL*num[a]*(num[a]-);
D=D+S[a];
loc++;
}
ans[Q[i].id]=D;
}
for(int i=; i<q; i++)
printf("%I64d\n",ans[i]);
}
return ;
}
04-25 07:19