City

https://codeforces.com/gym/103145/problem/K

题意：

由m条无向道路连接的n个城市，每条道路都有一个强度ki。敌人将进攻摧毁这些道路。当敌人发动伤害为x的攻击时，所有力量小于x的道路都将被摧毁。现在有Q个问题要问你，如果敌人发动伤害为pi的攻击，有多少对城市可以到达。城市x和城市y是可到达的，这意味着有一条从x到y的路径，并且该路径中每条道路的强度大于或等于pi。

题解：贪心+并查集

对于每个询问，我们可以看做每次把大于等于qi的路添加进去；

我们可以按照每条路的强度从大到小排序，q个询问也按照pi从大到小排序，这样既可以去掉重复的pi多次查询，也贪心去添加大于pi的路；然后每次添加路的时候，再使用并查集，就知道u,v是否已经在一个集合中，

如果在一个集合中，就不需要操作了；反之则需要把u,v添加到相同集合中；

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N],mp[N],n,m,q,ans[N],cnt,sum[N];//ans存储每次查询的对数，sum存储当前点为父节点的点数; 
struct node{
	ll u,v;
	ll w;
	bool operator <(const node &t){//每条路的强度从大到小排序
		return w>t.w;
	}
}edge[4*N];
struct node1{
	ll id;
	ll p;
	bool operator <(const node1 &t){//q个询问也按照pi从大到小排序
		return p>t.p;
	}
}nd[2*N];
void creat(){//初始并查集 
	for(ll i=1;i<=n;i++){
		a[i]=i; 
		sum[i]=1;
		ans[i]=0;
	}
}
int find(int x) {
    if(x!=a[x]) a[x]=find(a[x]);
	return a[x]; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>q;
		creat();
		cnt=0;
		nd[0].p=0,nd[0].id=0;
		for(int i=1;i<=m;i++){
			ll u,v,w;
			cin>>u>>v>>w;
			edge[++cnt]={u,v,w};
		}
		sort(edge+1,edge+1+cnt);
		for(int i=1;i<=q;i++){
			cin>>nd[i].p;
			nd[i].id=i;
		}
		sort(nd+1,nd+1+q);
		int j=1;
		for(int i=1;i<=q;i++){
			ll ans1=0;
			ans1=ans[nd[i-1].id];
			for(;j<=cnt;j++){
				if(edge[j].w<nd[i].p) break;//如果比当前查询的的要小就退出 
				ll u,v,w;
				u=edge[j].u;
				v=edge[j].v;
				w=edge[j].w;
				ll k1,k2;
				k1=find(u);
				k2=find(v);
				if(a[k1]!=a[k2]){//需要合并 
					ans1=ans1-(sum[a[k1]]*(sum[a[k1]]-1)/2+sum[a[k2]]*(sum[a[k2]]-1)/2);//减去原来的a[k1]的对数和原来的a[k2]的对数
					sum[a[k1]]+=sum[a[k2]];//把集合a[k2]的点数加入到a[k1]; 
					ans1+=sum[a[k1]]*(sum[a[k1]]-1)/2;//把新的a[k1]的对数重新计算加入 
					sum[a[k2]]=0;//把集合a[k2]变为0; 
					a[k2]=a[k1];//合并 
				}
			}
			ans[nd[i].id]=ans1;
		}
		for(int i=1;i<=q;i++){
			cout<<ans[i]<<endl;//输出每次查询 
		}
	}
	return 0;
}