Travel HDU - 5441

本文主要是介绍Travel HDU - 5441，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=5441

每次一个询问 给一个x 用所给边中值小于等于x的构图 问有多少点对是互相可达的

x显然要离线处理 多少点对的问题可以想到并查集搞一下

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
const int maxm=1e5+10;
const int maxq=5e3+10;struct node1
{int u,v,w;
};struct node2
{int id,x;
};node1 pre[maxm];
node2 order[maxq];
int f[maxn],cnt[maxn],ans[maxq];
int n,m,q;bool cmpI(node1 n1,node1 n2)
{return n1.w<n2.w;
}bool cmpII(node2 n1,node2 n2)
{return n1.x<n2.x;
}int getf(int p)
{if(f[p]==p) return p;else return f[p]=getf(f[p]);
}int unite(int u,int v)
{int res,fu,fv;fu=getf(u),fv=getf(v);if(fu!=fv){res=cnt[fu]*cnt[fv];f[fv]=fu,cnt[fu]+=cnt[fv];return res;}else return 0;
}int main()
{int t,i,j,val;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&q);for(i=1;i<=m;i++) scanf("%d%d%d",&pre[i].u,&pre[i].v,&pre[i].w);sort(pre+1,pre+m+1,cmpI);for(i=1;i<=n;i++) f[i]=i,cnt[i]=1;for(i=1;i<=q;i++){order[i].id=i;scanf("%d",&order[i].x);}sort(order+1,order+q+1,cmpII);j=1,val=0;for(i=1;i<=q;i++){ans[order[i].id]=val;while(j<=m&&pre[j].w<=order[i].x){ans[order[i].id]+=unite(pre[j].u,pre[j].v);j++;}val=ans[order[i].id];}for(i=1;i<=q;i++) printf("%d\n",2*ans[i]);}return 0;
}

 

这篇关于Travel HDU - 5441的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---