正題

---

題目大意

$n$個點$m$條邊，$q$次詢問走邊權小于$x$的能聯通的點對數。

---

解題思路

將邊權排序，然后并查集預處理答案即可。

時間復雜度$O(m\log m)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; struct node{ll x,y,w; }e[N]; ll T,n,m,q,fa[N],siz[N],ans[N]; bool cmp(node x,node y) {return x.w<y.w;} ll find(ll x) {return (fa[x]==x)?(x):(fa[x]=find(fa[x]));} int main() {scanf("%lld",&T);while(T--){memset(ans,0,sizeof(ans));scanf("%lld%lld%lld",&n,&m,&q);for(ll i=1;i<=n;i++)fa[i]=i,siz[i]=1;for(ll i=1;i<=m;i++)scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].w); sort(e+1,e+1+m,cmp);for(ll i=1;i<=m;i++){ll x=find(e[i].x),y=find(e[i].y);if(x==y)continue;ans[e[i].w]+=siz[x]*siz[y]*2;fa[y]=x;siz[x]+=siz[y];}for(ll i=1;i<=1e5;i++)ans[i]+=ans[i-1]; for(ll i=1;i<=q;i++){ll x;scanf("%lld",&x);printf("%lld\n",ans[x]);}} }

總結

以上是生活随笔為你收集整理的jzoj4223-旅游【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。