并查集+二分-hdu-4750-Count The Pairs
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4750
题目大意：
给一无向图，n个点，m条边，每条边有个长度，且不一样。定义f(i,j)表示从节点i到节点j的所有路径中的最大边权值的最小值。有q个询问，每个询问有个t,求f(i,j)>=t的种数。
解题思路：
并查集+简单dp+二分。
比赛的时候各种TLE和MLE。只是查找方式不对。
队友思路，先按边从小到大排序考虑，对于每条边E该边两个节点为a、b,如果a、b不在同一个联通块，则a联通块中点集A和b联通块中点集B的f值一定为E（因为E升序）。恰好能使其通路。
map[i]表示以权值为i的边作为f值的点对个数。
sum[i]表示以大于等于第i大边权值的权值作为f值得点对总的个数。
对于每一个t,在排序了的sig[i](能取的边权值）中二分找到大于等于它的最小的小标j。输出sum[j]即可。
注意：
求点对个数时要乘以2.
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#define eps 1e-6#define INF 0x3fffffff#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 11000#define Maxm 510000struct Edge{ int a,b,c;}edge[Maxm];map<int,int>myp;short int fa[Maxn],num[Maxn];int n,m;int sum[Maxm],sig[Maxm];bool cmp(struct Edge aa,struct Edge bb){ return aa.c<bb.c; //对边排序}int find(int x) //并查集 路径压缩{ int tmp=x; while(x!=fa[x]) x=fa[x]; while(fa[tmp]!=x) { int tt=fa[tmp]; fa[tmp]=x; tmp=tt; } return x;}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%d%d",&n,&m)) { int a,b,c; myp.clear(); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); edge[i].a=a,edge[i].b=b,edge[i].c=c; sig[i]=c; } sort(edge+1,edge+m+1,cmp); for(int i=0;i<=n;i++) { fa[i]=i; num[i]=1; //以i为根的联通块点的个数 } for(int i=1;i<=m;i++) { int ra=find(edge[i].a); int rb=find(edge[i].b); if(ra!=rb) //不在一个联通块内，两个块内的点通过该边连接，f值为该边 { if(myp.find(edge[i].c)!=myp.end()) myp[edge[i].c]=myp[edge[i].c]+num[ra]*num[rb]*2; else myp[edge[i].c]=num[ra]*num[rb]*2; fa[rb]=ra; //合并 num[ra]+=num[rb]; } } int q; scanf("%d",&q); sort(sig+1,sig+m+1); //对边权值排序 memset(sum,0,sizeof(sum));//sum[i]表示以大于等于第i大边权值的权值作为f值得点对总的个数。 sum[m]=myp[sig[m]]; for(int i=m-1;i>=1;i--) sum[i]+=sum[i+1]+myp[sig[i]]; for(int i=1;i<=q;i++) { int tt; scanf("%d",&tt); int pos=lower_bound(sig+1,sig+m+1,tt)-sig;//二分查找位置 printf("%d\n",sum[pos]); } } return 0;}