The 15th Chinese Northeast Collegiate Programming Contest K.CITY 离线单调+并查集连通+优先队列

离线单调+并查集连通+优先队列"/>

The 15th Chinese Northeast Collegiate Programming Contest K.CITY 离线单调+并查集连通+优先队列

题意

n个节点，m条边，每条边都有权重，Q次询问，每次询问附带一个正整数x代表，有规模为x的军队，能通过权重>=x的路。如果两个节点能互相到达，则算一个有效对，求针对军队规模为x，有几个有效对。

解析

1. 很容易的发现每次询问附带的军队规模x具有单调性，x如果越大，答案越小，反之答案越大。那么可以离线存储询问，对询问的规模进行排序，从规模大开始计算，然后越来越小，答案递增。
2. 对于一个确定大小为 s s s的连通块，其对答案贡献是固定的为 s ∗ ( s − 1 ) 2 \frac{s*(s-1)}{2} 2s∗(s−1)​，对于某两个连通块，因为x变小了，使得两个连通块链接在一起，变得更大了，我们只需要减去原两个的贡献度，维护连通块的算法当然是——并查集！
3. 那么问题来了，我们如何根据答案变小而找出影响了哪些边呢？很简单用优先队列存边即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll f[N];
ll sz[N];
pair<int,int> qs[N];
ll ans[N];
int find(int i){return f[i]==i? i: f[i]=find(f[i]);
}
ll merge(int a,int b){if(a>b)swap(a,b);int fa=find(a),fb=find(b);f[fa]=fb;sz[fb]+=sz[fa];return sz[fb];
}
struct edge{ll u,v,w;bool operator < (const edge a)const{return  w<a.w;}
};
ll get(ll x){return x*(x-1)/2;
}
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++){f[i]=i;sz[i]=1;}priority_queue<edge,vector<edge>>pq;for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);pq.push({u,v,w});}for(int i=1;i<=q;i++){scanf("%d",&qs[i].first);qs[i].second=i;}sort(qs+1,qs+1+q,greater<pair<int,int>>());ll res=0;
//        cout<<qs[1].first<<" "<<pq.top().w<<endl;for(int i=1;i<=q;i++){int x=qs[i].first;while(!pq.empty() && pq.top().w>=x){auto t=pq.top();pq.pop();int u=t.u;int v=t.v;if(find(u)!=find(v)){res-=get(sz[find(u)])+get(sz[find(v)]);res+=get(merge(u,v));}}ans[qs[i].second]=res;}for(int i=1;i<=q;i++){cout<<ans[i]<<endl;}}
}